A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints

Okan Arslan (), Ola Jabali () and Gilbert Laporte ()
Additional contact information
Okan Arslan: HEC Montréal, Montreal, Quebec H3T 2A7, Canada
Ola Jabali: Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, 20133 Milan, Italy
Gilbert Laporte: HEC Montréal, Montreal, Quebec H3T 2A7, Canada

INFORMS Journal on Computing, 2020, vol. 32, issue 1, 120-134

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.

Keywords: network design; survivability; vulnerability; branch-and-cut algorithm; length-bounded minimum cut (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0869 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:1:p:120-134

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().