TY - JOUR
T1 - A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints
AU - Arslan, Okan
AU - Jabali, Ola
AU - Laporte, Gilbert
N1 - Funding Information:
History: Accepted by S. Raghavan, Area Editor for Network Optimization: Algorithms & Applications. Funding: The authors gratefully acknowledge funding provided by the Canadian Natural Sciences and Engineering Research Council [Grants 436014-2013 and 2015-06189] and the Fonds de Recherche du Québec-Nature et Technologies [Grant NC-198837]. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2018.0869.
Publisher Copyright:
©2019 INFORMS.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/3
Y1 - 2020/3
N2 - Given a graph, a set of origin-destination (OD) pairs with communication requirements, and an integer k 2, the network design problem with vulnerability constraints (NDPVC) is to identify a subgraph with the minimum total edge costs such that, between each OD pair, there exist a hop-constrained primary path and a hop-constrained backup path after any k â' 1 edges of the graph fail. Formulations exist for single-edge failures (i.e., k = 2). To solve the NDPVC for an arbitrary number of edge failures, we develop two natural formulations based on the notion of length-bounded cuts. We compare their strengths and flexibilities in solving the problem for k 3. We study different methods to separate infeasible solutions by computing length-bounded cuts of a given size. Experimental results show that, for single-edge failures, our formulation increases the number of solved benchmark instances from 61% (obtained within a two-hour limit by the best published algorithm) to more than 95%, thus increasing the number of solved instances by 1,065. Our formulation also accelerates the solution process for larger hop limits and efficiently solves the NDPVC for general k. We test our best algorithm for two to five simultaneous edge failures and investigate the impact of multiple failures on the network design. Â
AB - Given a graph, a set of origin-destination (OD) pairs with communication requirements, and an integer k 2, the network design problem with vulnerability constraints (NDPVC) is to identify a subgraph with the minimum total edge costs such that, between each OD pair, there exist a hop-constrained primary path and a hop-constrained backup path after any k â' 1 edges of the graph fail. Formulations exist for single-edge failures (i.e., k = 2). To solve the NDPVC for an arbitrary number of edge failures, we develop two natural formulations based on the notion of length-bounded cuts. We compare their strengths and flexibilities in solving the problem for k 3. We study different methods to separate infeasible solutions by computing length-bounded cuts of a given size. Experimental results show that, for single-edge failures, our formulation increases the number of solved benchmark instances from 61% (obtained within a two-hour limit by the best published algorithm) to more than 95%, thus increasing the number of solved instances by 1,065. Our formulation also accelerates the solution process for larger hop limits and efficiently solves the NDPVC for general k. We test our best algorithm for two to five simultaneous edge failures and investigate the impact of multiple failures on the network design. Â
KW - branch-and-cut algorithm
KW - length-bounded minimum cut
KW - Network design
KW - survivability
KW - vulnerability
UR - http://www.scopus.com/inward/record.url?scp=85091755540&partnerID=8YFLogxK
U2 - 10.1287/IJOC.2018.0869
DO - 10.1287/IJOC.2018.0869
M3 - Article
AN - SCOPUS:85091755540
SN - 1091-9856
VL - 32
SP - 120
EP - 134
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
IS - 1
ER -