TY - JOUR

T1 - Design of Survivable Networks with Vulnerability Constraint

AU - Gouveia, Luis

AU - Leitner, M.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Hop-constraints

KW - Integer programming

KW - Networks

KW - OR in telecommunications

KW - Survivable network design

UR - http://www.scopus.com/inward/record.url?scp=84992724156&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84992724156&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2016.09.003

DO - 10.1016/j.ejor.2016.09.003

M3 - Article

VL - 258

SP - 89

EP - 103

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -