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

Okan Arslan, Ola Jabali, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

5 Citations (SciVal)
133 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

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

Fingerprint

Dive into the research topics of 'A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints'. Together they form a unique fingerprint.

Cite this