- Ralf Borndörfer, ZIB Berlin, Germany
"Configuration Models in Transport Optimization"
Configurations are local solutions of network
optimization problems that can be used to assemble an overall solution.
They are used to express complex requirements, that would be hard to
formulate using constraints, by means of a local and hence manageable
enumeration of ``feasible configurations''. This gives rise to an
extended formulation involving additional configuration variables.
Usually, one has to make choices between several possible
configurations, such that
configuration models are often of a set
packing, partitioning, or covering type. Such a formulation is
combinatorially clean and lends itself to column generation techniques.
If the configurations capture a core aspect of the problem, such a
model will be provably strong, if the configurations can be computed
efficiently, it is algorithmically tractable. Typical examples of
configuration models come up in transport optimization, where the
integrated treatment of technical
etc. constraints or the
simultaneous solution of multi-stage models is a major challenge.
Successful applications include railway track allocation, leading to
path packing configuration models, railway rotation planning, resulting
in hypergraph assignment and flow models, and depot management as well
as line planning, leading to set partitioning type models. All of these
models provide strong LP bounds and can be solved efficiently for large
scale real-world problems. The talk surveys these results.
based on joint work with Martin Grötschel, Olga Heismann, Heide
Hoppmann, Marika Karbstein, Torsten Klug, Markus Reuther, Thomas
Schlechte, Elmar Swarat, and Steffen Weider.