Integer programming models and branch-and-cut approaches to generalized {0,1,2}-survivable network design problems

Markus Leitner*

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

In this article, we introduce the Generalized { 0 , 1 , 2 } -Survivable Network Design Problem ({ 0 , 1 , 2 } -GSNDP) which has applications in the design of backbone networks. Different mixed integer linear programming formulations are derived by combining previous results obtained for the related { 0 , 1 , 2 } -GSNDP and Generalized Network Design Problems. An extensive computational study comparing the correspondingly developed branch-and-cut approaches shows clear advantages for two particular variants. Additional insights into individual advantages and disadvantages of the developed algorithms for different instance characteristics are given.

Original languageEnglish
Pages (from-to)73-92
Number of pages20
JournalComputational Optimization and Applications
Volume65
Issue number1
DOIs
Publication statusPublished - 1 Sep 2016
Externally publishedYes

Keywords

  • Biconnectivity
  • Branch-and-cut
  • Generalized network design
  • Mixed integer linear programming
  • Survivability

Fingerprint

Dive into the research topics of 'Integer programming models and branch-and-cut approaches to generalized {0,1,2}-survivable network design problems'. Together they form a unique fingerprint.

Cite this