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

Okan Arslan, Ola Jabali, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)

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 languageEnglish
Pages (from-to)120-134
Number of pages15
JournalINFORMS Journal on Computing
Volume32
Issue number1
DOIs
Publication statusPublished - Mar 2020

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

Cite this