Complexity of column generation in network design with path-based survivability mechanisms
Författare
Summary, in English
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.
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.
Avdelning/ar
Publiceringsår
2012
Språk
Engelska
Sidor
132-147
Publikation/Tidskrift/Serie
Networks
Volym
59
Issue
1
Dokumenttyp
Artikel i tidskrift
Förlag
John Wiley & Sons Inc.
Ämne
- Electrical Engineering, Electronic Engineering, Information Engineering
Nyckelord
- mixed-integer programing
- computational complexity
- column
- path
- generation
- survivable network design
Status
Published
Forskningsgrupp
- Networking
ISBN/ISSN/Övrigt
- ISSN: 1097-0037