Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
and
organization
publishing date
type
Contribution to conference
publication status
published
subject
conference name
International Network Optimization Conference INOC’2009
conference location
Pisa, Italy
conference dates
2009-04-26 - 2009-04-29
language
English
LU publication?
yes
additional info
(This paper is a short version of the technical report, see ZIB-Report 08-51, December 2008, http://opus.kobv.de/zib/volltexte/2008/1146/.)
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
2016-04-04 13:32:57
date last changed
2018-11-21 21:14:44
@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},
  url          = {http://www.di.unipi.it/optimize/Events/proceedings/T/B/3/TB3-5.pdf},
  year         = {2009},
}