@misc{Hoppmann, type = {Master Thesis}, author = {Hoppmann, Heide}, title = {A Configuration Model for the Line Planning Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51610}, pages = {108}, abstract = {In this thesis we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations are combinatorial building blocks of primal solutions; they rule out the "capacity numerics" and make the problem purely combinatorial. The concept of configurations can also be adapted to other capacitated network design problems. The configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, multicover, and MIR inequalities. These theoretical findings can be confirmed in computations, however, the enormous number of configurations can blow up the formulation for large instances. We propose a mixed model that enriches the standard model by a judiciously chosen subset of configurations that provide a good compromise between model strength and size. Computational results for large-scale line planning problems are presented.}, language = {en} }