Design of Survivable Networks with Vulnerability Constraint

Luis Gouveia, M. Leitner

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider the Network Design Problem with Vulnerability Constraints (NDPVC) which simultaneously addresses resilience against failures (network survivability) and bounds on the lengths of each communication path (hop constraints). Solutions to the NDPVC are subgraphs containing a path of length at most Hst for each commodity {s, t} and a path of length at most Hst' between s and t after at most k-1 edge failures. We first show that a related and well known problem from the literature, the Hop-Constrained Survivable Network Design Problem (kHSNDP), that addresses the same two measures produces solutions that are too conservative in the sense that they might be too expensive in practice or may even fail to provide feasible solutions. We also explain that the reason for this difference is that Mengerian-like theorems not hold in general when considering hop-constraints. Three graph theoretical characterizations of feasible solutions to the NDPVC are derived and used to propose integer linear programming formulations. In a computational study we compare these alternatives with respect to the lower bounds obtained from the corresponding linear programming relaxations and their capability of solving instances to proven optimality. In addition, we show that in many cases, the solutions produced by solving the NDPVC are cheaper than those obtained by the related kHSNDP.
Original languageEnglish
Pages (from-to)89-103
Number of pages15
JournalEuropean Journal of Operational Research
Volume258
Issue number1
DOIs
Publication statusPublished - 2017

Funding

This work is supported by National Funding from FCT - Fundação para a Ciência e a Tecnologia , under the project UID/MAT/04561/2013 , by the Austrian Science Fund (FWF) , under grant I892-N23 , and by the Vienna Science and Technology Fund (WWTF) through project ICT15-014 . Part of this research has been performed while M. Leitner was a research fellow at the Department of Computer Science, Université Libre de Bruxelles (Brussels, Belgium) where he was supported by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office. These supports are greatly acknowledged. This work is supported by National Funding from FCT - Funda??o para a Ci?ncia e a Tecnologia, under the project UID/MAT/04561/2013, by the Austrian Science Fund (FWF), under grant I892-N23, and by the Vienna Science and Technology Fund (WWTF) through project ICT15-014. Part of this research has been performed while M. Leitner was a research fellow at the Department of Computer Science, Universit? Libre de Bruxelles (Brussels, Belgium) where he was supported by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office. These supports are greatly acknowledged.

FundersFunder number
Ci?ncia e a Tecnologia
Department of Computer Science, Universit?
Vienna Science and Technology FundICT15-014
Fundação para a Ciência e a TecnologiaUID/MAT/04561/2013
Austrian Science FundI892-N23
Belgian Federal Science Policy Office
Université Libre de Bruxelles

    Keywords

    • Hop-constraints
    • Integer programming
    • Networks
    • OR in telecommunications
    • Survivable network design

    Fingerprint

    Dive into the research topics of 'Design of Survivable Networks with Vulnerability Constraint'. Together they form a unique fingerprint.

    Cite this