Abstract
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. Â
Original language | English |
---|---|
Pages (from-to) | 120-134 |
Number of pages | 15 |
Journal | INFORMS Journal on Computing |
Volume | 32 |
Issue number | 1 |
DOIs | |
Publication status | Published - Mar 2020 |
Bibliographical note
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.
Funding
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.
Keywords
- branch-and-cut algorithm
- length-bounded minimum cut
- Network design
- survivability
- vulnerability
ASJC Scopus subject areas
- Software
- Information Systems
- Computer Science Applications
- Management Science and Operations Research