A Branch-and-Cut algorithm for the Capacitated Multi-Failure Survivable Network Design problem. (October 2018)

• Record Type: Journal Article
• Authors: Borne, S.; Gourdin, E.; Klopfenstein, O.; Mahjoub, A.R.
• Is Part Of: Computers & industrial engineering. Volume 124(2018)
• Page Start: 582
• Page End: 603
• Publication Date: 2018-10
• Subjects: IP-over-optical network -- Survivability -- Capacities -- Polytope -- Facet -- Branch-and-Cut-and-Price algorithms; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.05.043
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A Survivable network design problem is considered from a polyhedral point of view. Integer programming formulations are provided. Valid inequalities are introduced and their facial structure is studied. Separation routines are proposed as well as a Branch-and-Cut-and-Price algorithm. Computational results are presented and discussed. Abstract: Telecommunication networks can be seen as the stacking of several layers like, for instance, IP-over-Optical networks. This infrastructure should have sufficient capacities to route some demands between their origin-destination nodes. In this paper we consider the Capacitated Multi-Failure Survivable Network Design problem. We study two variants of this problem with simple and multiple capacities. We give two multicommodity flow formulations for each variant of this problem and describe some valid inequalities. In particular, we characterize valid inequalities obtained using Chvatal-Gomory procedure from the well known Cutset inequalities. We show that some of these inequalities are facet defining. We discuss separation routines for all the valid inequalities. Using these results, we develop a Branch-and-Cut algorithm and a Branch-and-Cut-and-Price algorithm for each variant and present extensive computational results.