Advanced

Complexity of column generation in network design with path-based survivability mechanisms

Orlowski, S. and Pioro, Michal LU (2012) In Networks 59(1). p.132-147
Abstract (Swedish)
Abstract in Undetermined

his survey deals with computational complexity of column generation problems arising in the design of survivable communication networks. Such problems are often modeled as linear programs based on noncompact multicommodity flow network formulations. These formulations involve an exponential number of path-flow variables, and therefore require column generation to be solved to optimality. We consider several path-based protection and restoration mechanisms and present results, both known and new, on the complexity of the corresponding column generation (also called pricing) problems. We discuss results for the case of single link or single node failures scenarios, and extend the considerations to... (More)
Abstract in Undetermined

his survey deals with computational complexity of column generation problems arising in the design of survivable communication networks. Such problems are often modeled as linear programs based on noncompact multicommodity flow network formulations. These formulations involve an exponential number of path-flow variables, and therefore require column generation to be solved to optimality. We consider several path-based protection and restoration mechanisms and present results, both known and new, on the complexity of the corresponding column generation (also called pricing) problems. We discuss results for the case of single link or single 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. Eventually, we show that almost all the encountered pricing problems are hard to solve for scenarios admitting multiple failures, while a great deal of them are NP-hard already for single failure scenarios. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
mixed-integer programing, computational complexity, column, path, generation, survivable network design
in
Networks
volume
59
issue
1
pages
132 - 147
publisher
John Wiley & Sons
external identifiers
  • wos:000298087600012
  • scopus:83555166323
ISSN
1097-0037
DOI
10.1002/net.20484
language
English
LU publication?
yes
id
cabb45f1-63d7-42c0-b0f9-8d17956eae13 (old id 1720007)
date added to LUP
2010-11-22 10:41:15
date last changed
2017-01-15 03:43:29
@article{cabb45f1-63d7-42c0-b0f9-8d17956eae13,
  abstract     = {<b>Abstract in Undetermined</b><br/><br>
his survey deals with computational complexity of column generation problems arising in the design of survivable communication networks. Such problems are often modeled as linear programs based on noncompact multicommodity flow network formulations. These formulations involve an exponential number of path-flow variables, and therefore require column generation to be solved to optimality. We consider several path-based protection and restoration mechanisms and present results, both known and new, on the complexity of the corresponding column generation (also called pricing) problems. We discuss results for the case of single link or single 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. Eventually, we show that almost all the encountered pricing problems are hard to solve for scenarios admitting multiple failures, while a great deal of them are NP-hard already for single failure scenarios.},
  author       = {Orlowski, S. and Pioro, Michal},
  issn         = {1097-0037},
  keyword      = {mixed-integer programing,computational complexity,column,path,generation,survivable network design},
  language     = {eng},
  number       = {1},
  pages        = {132--147},
  publisher    = {John Wiley & Sons},
  series       = {Networks},
  title        = {Complexity of column generation in network design with path-based survivability mechanisms},
  url          = {http://dx.doi.org/10.1002/net.20484},
  volume       = {59},
  year         = {2012},
}