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.
Citation
University of Vienna, Austria, 05/2017