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
SN - 0377-2217
VL - 258
SP - 89
EP - 103
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -