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)

http://www.ism.ac.jp/access/index_e.html

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
梅谷俊治
(大阪大学大学院情報科学研究科情報数理学専攻)

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

アブストラクト:
集合分割問題は,与えられた集合の全ての要素をちょうど1回ずつ含む部分集合
の組み合わせの中で,コストの総和が最小となるものを求める組合せ最適化問題
であり,乗務員スケジューリング,配送計画問題,施設配置問題など多くの現実
問題を応用に持つ.集合分割問題は制約条件を満たす解を求めることも難しく,
緩和問題を利用した 手法で良い解が得られない場合も少なくないため,NP困難
な組合せ最適化問題の中でも特に計算困難な問題として知られている.本研究で
は,大規模な集合分割問題に対して精度の良い近似解を効率良く求める 局所探
索法を提案する.提案手法では,同じ制約条件に同時に現れる頻度の高い変数の
組を列挙してリストに記憶することで,複数の変数値を同時に反転する大きな近
傍の効率的な探索を実現し,約227万変数の大規模な問題例でも精度の高い近似
解が得られることを数値実験で示した.