Optimization Online


Branch-and-cut methods for the Network Design Problem with Vulnerability Constraints

Luís Gouveia (legouveia***at***fc.ul.pt)
Martim Joyce-Moniz (martim.joyce-moniz***at***gerad.ca)
Markus Leitner (markus.leitner***at***univie.ac.at)

Abstract: The aim of Network Design Problem with Vulnerability Constraints (NDPVC), introduced by Gouveia and Leitner [EJOR, 2017], is to design survivable telecommunications networks that impose length bounds on the communication paths of each commodity pair, before and after the failure of any k links. This problem was proposed as an alternative to the Hop-Constrained Survivable Network Design Problem (kHSNDP), which addresses similar issues, but imposes very conservative constraints, possibly leading to unnecessarily expensive solution or even rendering instances infeasible. It was shown that the cost of the optimal solutions of the NDPVC never exceeds that of the related kHSNDP. However, results reported by Gouveia and Leitner [EJOR, 2017] using the standard methods of a general-purpose integer linear (ILP) solver, along with several ILP formulations, show that such methods fail to solve most instances in the benchmarking test set. In this paper, we propose three branch-and-cut methods, based on graph-theoretical characterizations introduced by Gouveia and Leitner [EJOR, 2017], which are significantly more efficient in solving the NDPVC. With the proposed new methods, we are able to solve substantially more instances of the NDPVC and therefore able to provide a more complete comparison of its solutions to those of the kHSNDP.

Keywords: Networks; Integer programming; Survivable network design; Hop-constraints; OR in telecommunications; Benders decomposition

Category 1: Network Optimization

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Applications -- OR and Management Sciences (Telecommunications )

Citation: University of Vienna, Austria, 05/2017

Download: [PDF]

Entry Submitted: 05/16/2017
Entry Accepted: 05/16/2017
Entry Last Modified: 05/16/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society