On the complexity of column generation in survivable network design with path-based survivability mechanisms
- Sebastian Orlowski,
- Michał Pióro
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.
- Record ID
- Scutellà Maria Grazia, Maria Grazia Scutellà Gouveia Luis Luis Gouveia (eds.): INOC 2009 - International Network Optimization Conference , 2009, Pisa, Italy, Wiley, 189 p.
- Keywords in English
- network design, routing, column generation, complexity, multiple failures
- http://www.di.unipi.it/optimize/Events/proceedings/T/B/3/TB3-5.pdf Opening in a new tab
- Project (archive)
- Graphs and Algorithms in Communication Networks. Project leader: Pióro Michał, +48 22 234 73 83, application date 28-03-2006, start date 30-05-2006, end date 29-05-2009, IT/2006/badawczy/02, CompletedWEiTI
- European Network of the Future: Anticipating the Network of the Future - From Theory to Design. Project leader: Pióro Michał, +48 22 234 73 83, start date 01-01-2008, end date 30-06-2012, IT/2008/7PR/05, CompletedWEiTI7 Framework Programme (7 FP) [7 Program Ramowy (7 PR)]
- (en) English
- File: 1
- Score (nominal)
- Uniform Resource Identifier
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.