Advanced

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

Orlowski, Sebastian and Pioro, Michal LU (2009) International Network Optimization Conference INOC’2009
Abstract
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to conference
publication status
published
subject
conference name
International Network Optimization Conference INOC’2009
language
English
LU publication?
yes
id
c862431a-5a77-4694-81f3-689fdaea67e0 (old id 1364611)
alternative location
http://www.di.unipi.it/optimize/Events/proceedings/T/B/3/TB3-5.pdf
date added to LUP
2009-03-24 09:23:17
date last changed
2016-09-30 15:22:33
@misc{c862431a-5a77-4694-81f3-689fdaea67e0,
  abstract     = {This paper deals with path-based linear programming formulations in survivable network design. In a recent<br/><br>
survey we have investigated the complexity of the column generation problems for a large variety of protection<br/><br>
and restoration mechanisms in a single or multiple link failure scenario, and classified them according to their<br/><br>
structure. It turned out that all the considered column generation problems are composed of only few building<br/><br>
blocks which determine their complexity. In this paper, we summarize our findings and give an example for each<br/><br>
of these building blocks.},
  author       = {Orlowski, Sebastian and Pioro, Michal},
  language     = {eng},
  title        = {On the complexity of column generation in survivable network design with path-based survivability mechanisms},
  year         = {2009},
}