TY - GEN A1 - Orlowski, Sebastian A1 - Pióro, Michal T1 - On the complexity of column generation in survivable network design with path-based survivability mechanisms N2 - 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. T3 - ZIB-Report - 08-51 KW - Netzplanung KW - Dimensionierung KW - Spaltengenerierung KW - Mehrfachausfälle KW - survivable network design KW - routing KW - column generation KW - pricing KW - complexity Y1 - 2008 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1105 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-11058 SN - 1438-0064 ER -