Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

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

Publiceringsår: 2008
Språk: Engelska
Publikation/Tidskrift/Serie: ZIB-Report
Volym: 08-51
Dokumenttyp: Rapport
Förlag: Warsaw University of Technology


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.


  • Electrical Engineering, Electronic Engineering, Information Engineering


  • Networking-lup-obsolete
  • ISSN: 1438-0064

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen