Benders decomposition for the hop-constrained survivable network design problem

Quentin Botton (), Bernard Fortz (), Luis Gouveia () and Michael Poss ()
Additional contact information
Quentin Botton: Université catholique de Louvain, CESCM-LSM and CORE, B-1348 Louvain-la-Neuve, Belgium
Bernard Fortz: GOM, Université Libre de Bruxelles, Belgium
Luis Gouveia: Universidade de Lisboa, DEIO, P-1749-016 Lisbon, Portugal
Michael Poss: GOM, Université Libre de Bruxelles, Belgium

No 2011037, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: Given a graph with nonnegative edge weights and node pairs Q, we study the problem of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. Using the layered representation introduced by Gouveia (1998), we present a formulation for the problem valid for any K, L ≥ 1. We use a Benders decomposition method to efficiently handle the big number of variables and constraints. We show that our Benders cuts contain the constraints used by Huygens et al. to formulate the problem for L = 2,3,4, as well as new inequalities when L ≥ 5. While some recent works on Benders decomposition study the impact of the normalization constraint in the dual subproblem, we focus here on when to generate the Benders cuts. We present a thorough computational study of various branch-and-cut algorithms on a large set of instances including the real based instances from SNDlib. Our best branch-and-cut algorithm combined with an efficient heuristic is able to solve the instances significantly faster than CPLEX 12 on the extended formulation.

Keywords: network design; survivability; hop-constraints; benders decomposition; branch-and-cut algorithms (search for similar items in EconPapers)
JEL-codes: C10 C57 M10 (search for similar items in EconPapers)
Date: 2011-09-01
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2011.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2011037

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().