Branch-and-cut methods for the network design problem with vulnerability constraints

Luis Gouveia, M. Leitner, Martim Joyce-Moniz

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The aim of Network Design Problem with Vulnerability Constraints (NDPVC), 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. In fact, it is known that the cost of the optimal solutions of the NDPVC never exceeds that of the related kHSNDP. However, previous results using the standard methods of a general-purpose integer linear (ILP) solver, combined with several ILP formulations, show that such methods fail to solve most instances in the benchmarking test set, within a time limit of two hours.

In this paper, we propose three branch-and-cut algorithms, which are significantly more efficient in solving the NDPVC. The first algorithm is a cutting-plane method devised in the context of a new layered graph ILP formulation, whereas the other two are based on Benders decomposition methods of previously known formulations. 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.
Original languageEnglish
Pages (from-to)190-208
Number of pages19
JournalComputers and Operations Research
Volume91
DOIs
Publication statusPublished - 2018

Funding

This work has been supported by the Portuguese National Funding from Fundação para a Ciência e a Tecnologia, under project UID/MAT/04561/2013 (L. Gouveia), by the Austrian Science Fund (FWF), under grant I892-N23 (M. Joyce-Moniz), and by the Vienna Science and Technology Fund (WWTF) through project ICT15-014 (M. Leitner). These supports are greatly acknowledged.

FundersFunder number
Vienna Science and Technology FundICT15-014
Fundação para a Ciência e a TecnologiaUID/MAT/04561/2013
Austrian Science FundI892-N23

    Fingerprint

    Dive into the research topics of 'Branch-and-cut methods for the network design problem with vulnerability constraints'. Together they form a unique fingerprint.

    Cite this