On the complexity of column generation in survivable network design with path-based survivability mechanisms
(2008) In ZIB-Report- Abstract
- 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... (More) - 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1364593
- author
- Orlowski, Sebastian and Pioro, Michal LU
- organization
- publishing date
- 2008
- type
- Book/Report
- publication status
- published
- subject
- in
- ZIB-Report
- publisher
- Warsaw University of Technology
- report number
- 08-51
- ISSN
- 1438-0064
- language
- English
- LU publication?
- yes
- id
- c2b2b218-5698-4939-83cc-e970f28745d2 (old id 1364593)
- date added to LUP
- 2016-04-01 13:13:40
- date last changed
- 2018-11-21 20:13:52
@techreport{c2b2b218-5698-4939-83cc-e970f28745d2,
abstract = {{This survey concerns optimization problems arising in the design<br/><br>
of survivable communication networks. It turns out that such<br/><br>
problems can be modeled in a natural way as non-compact linear<br/><br>
programming formulations based on multicommodity flow network<br/><br>
models. These non-compact formulations involve an exponential<br/><br>
number of path flow variables, and therefore require column<br/><br>
generation to be solved to optimality. We consider several<br/><br>
path-based survivability mechanisms and present results, both<br/><br>
known and new, on the complexity of the corresponding column<br/><br>
generation problems (called the pricing problems). We discuss<br/><br>
results for the case of the single link (or node) failures<br/><br>
scenarios, and extend the considerations to multiple link<br/><br>
failures. Further, we classify the design problems corresponding<br/><br>
to different survivability mechanisms according to the structure<br/><br>
of their pricing problem. Finally, we show that almost all<br/><br>
encountered pricing problems are hard to solve for scenarios<br/><br>
admitting multiple failures.}},
author = {{Orlowski, Sebastian and Pioro, Michal}},
institution = {{Warsaw University of Technology}},
issn = {{1438-0064}},
language = {{eng}},
number = {{08-51}},
series = {{ZIB-Report}},
title = {{On the complexity of column generation in survivable network design with path-based survivability mechanisms}},
year = {{2008}},
}