Strong lower bounds for a survivable network design problem

Markus Leitner*, Günther R. Raidl

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider a generalization of the Prize Collecting Steiner Tree Problem on a graph with special redundancy requirements on a subset of the customer nodes suitable to model a real world problem occurring in the extension of fiber optic communication networks. We strengthen an existing connection-based mixed integer programming formulation involving exponentially many variables using a recent result with respect to the orientability of two-node connected graphs. The linear programming relaxation of this model is then solved by means of column generation. We show that our new model is theoretically stronger than a previously described one and present promising preliminary computational results.

Original languageEnglish
Pages (from-to)295-302
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Volume36
Issue numberC
DOIs
Publication statusPublished - 1 Aug 2010
Externally publishedYes

Keywords

  • Column generation
  • Mixed integer programming
  • Survivable network design

Fingerprint Dive into the research topics of 'Strong lower bounds for a survivable network design problem'. Together they form a unique fingerprint.

Cite this