Configuration Models in Transport Optimization

Ralf Borndörfer^*

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. It is 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.

Mathematics Subject Classification: 90C10 90B06

Keywords: Configurations, extended formulations, column generation, traffic and transport optimization

Plenary Lecture