Advanced

On the complexity of column generation in survivable network design with path-based survivability mechanisms

Orlowski, Sebastian and Pioro, Michal LU (2008) In ZIB-Report 08-51.
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:
author
organization
publishing date
type
Book/Report
publication status
published
subject
in
ZIB-Report
volume
08-51
publisher
Warsaw University of Technology
ISSN
1438-0064
language
English
LU publication?
yes
id
c2b2b218-5698-4939-83cc-e970f28745d2 (old id 1364593)
date added to LUP
2009-03-24 09:23:05
date last changed
2016-09-30 15:22:33
@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},
  series       = {ZIB-Report},
  title        = {On the complexity of column generation in survivable network design with path-based survivability mechanisms},
  volume       = {08-51},
  year         = {2008},
}