The 13th Statistical Machine Learning Seminar (2013.11.21)

Date/time: Nov. 21st (Thu) 14:45-16:45
Place: Seminar Room 5 (3F, D313 & D314),
Institute of Statistical Mathematics (Tachikawa, Tokyo)

Speaker 1
Ralf Borndörfer (Zuse-Institut Berlin)

Title: Railway Optimization and Integer Programming

Abstract: Railways are a classical and yet extremely active application
area of combinatorial optimization and integer programming. Large
networks, complex technical requirements, evolving demand patterns, and
changes in the regulatory framework give rise to challenging
optimization problems, which call for the development of new
mathematical models and algorithms. There is, in particular, a need for
a simultaneous treatment of multiple aspects, i.e., an integration of
decisions about routing, scheduling, train composition, maintenance,
parking, transfers, etc.
This talk proposes “configuration models” as a novel approach to such
problems. Configurations are local building blocks of primal solutions.
The idea is to model involved requirements, that would be difficult to
express in terms of constraints, using an exhaustive, but local, and
hence manageable, enumeration of variables. This often gives rise to
large, but combinatorially clean packing and covering type models, and
it often produces strong LP bounds. Examples of successful applications
of this method include railway track allocation (the configurations are
occupations of track segments over time), vehicle rotation planning (the
configurations correspond to train compositions), and line planning (
configurations correspond to line bundles on an infrastructure segments).
Configuration models lend themselves to column generation approaches,
which can be complemented by problem specific methods.
The talk discusses the case of track allocation, in which the master
problem is about path packing, and the case vehicle rotation planning,
in which the master problem is about flows in hypergraphs. Results for
saturating the capacity of the Simplon tunnel through the Alps and for
scheduling the ICE high-speed train fleet in Germany will be reported.
This talk is based on joint work with Martin Gr¨otschel, Olga Heismann,
Torsten Klug, Markus Reuther, Thomas Schlechte, Elmar Swarat, and
Steffen Weider.

Speaker 2

タイトル: 大規模な集合分割問題に対する局所探索法

緩和問題を利用した 手法で良い解が得られない場合も少なくないため,NP困難
は,大規模な集合分割問題に対して精度の良い近似解を効率良く求める 局所探