A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints
Okan Arslan, Ola Jabali, Gilbert Laporte
INFORMS Journal on Computing · 2020 · Volume 32 · Issue 1
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
Enable JavaScript for citation tools and additional paper interactions.