On the complexity of column generation in survivable network design with path-based survivability mechanisms
Sebastian Orlowski, Michał Pióro · 2008
This paper deals with path-based linear programming formulations in survivable network design. In a recent survey we have investigated the complexity of the column generation problems for a large variety of protection and restoration mechanisms in a single or multiple link failure scenario, and classified them according to their structure. It turned out that all the considered column generation problems are composed of only few building blocks which determine their complexity. In this paper, we summarize our findings and give an example for each of these building blocks.