On the complexity of column generation in survivable network design with path-based survivability mechanisms
Author
Summary, in English
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.
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.
Publishing year
2009
Language
English
Links
Document type
Conference paper
Topic
- Electrical Engineering, Electronic Engineering, Information Engineering
Conference name
International Network Optimization Conference INOC’2009
Conference date
2009-04-26 - 2009-04-29
Conference place
Pisa, Italy
Status
Published
Research group
- Networking