• search hit 2 of 18
Back to Result List

On the complexity of column generation in survivable network design with path-based survivability mechanisms

Please always quote using this URN: urn:nbn:de:0297-zib-11058
  • This survey concerns optimization problems arising in the design of survivable communication networks. It turns out that such problems can be modeled in a natural way as non-compact linear programming formulations based on multicommodity flow network models. These non-compact formulations involve an exponential number of path flow variables, and therefore require column generation to be solved to optimality. We consider several path-based survivability mechanisms and present results, both known and new, on the complexity of the corresponding column generation problems (called the pricing problems). We discuss results for the case of the single link (or node) failures scenarios, and extend the considerations to multiple link failures. Further, we classify the design problems corresponding to different survivability mechanisms according to the structure of their pricing problem. Finally, we show that almost all encountered pricing problems are hard to solve for scenarios admitting multiple failures.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Sebastian Orlowski, Michal Pióro
Document Type:ZIB-Report
Tag:Dimensionierung; Mehrfachausfälle; Netzplanung; Spaltengenerierung
column generation; complexity; pricing; routing; survivable network design
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Mxx Computer system organization / 68M10 Network design and communication [See also 68R10, 90B18]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C08 Special problems of linear programming (transportation, multi-index, etc.)
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
Contributing Corporation:Warsaw University of Technology
Date of first Publication:2008/12/18
Series (Serial Number):ZIB-Report (08-51)
ISSN:1438-0064