Benders decomposition for the hop-constrained survivable network design problem
AbstractGiven 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) in its series CORE Discussion Papers with number 2011037.
Date of creation: 01 Sep 2011
Date of revision:
Contact details of provider:
Postal: Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium)
Fax: +32 10474304
Web page: http://www.uclouvain.be/core
More information through EDIRC
network design; survivability; hop-constraints; benders decomposition; branch-and-cut algorithms;
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Pirkul, Hasan & Soni, Samit, 2003. "New formulations and solution procedures for the hop constrained network design problem," European Journal of Operational Research, Elsevier, vol. 148(1), pages 126-140, July.
- Duranton, Gilles & Martin, Philippe & Mayer, Thierry & Mayneris, Florian, 2010. "The Economics of Clusters: Lessons from the French Experience," OUP Catalogue, Oxford University Press, number 9780199592203.
- Belleflamme,Paul & Peitz,Martin, 2010. "Industrial Organization," Cambridge Books, Cambridge University Press, number 9780521681599, November.
- Fleurbaey,Marc & Maniquet,François, 2011.
"A Theory of Fairness and Social Welfare,"
Cambridge University Press, number 9780521887427, November.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Alain GILLIS).
If references are entirely missing, you can add them using this form.