The survivable k-node-connected network design problem: Valid inequalities and Branch-and-Cut. (October 2017)

• Record Type: Journal Article
• Authors: Mahjoub, Meriem; Diarrassouba, I.; Mahjoub, A.R.; Taktak, R.
• Is Part Of: Computers & industrial engineering. Volume 112(2017)
• Page Start: 690
• Page End: 705
• Publication Date: 2017-10
• Subjects: k-node-connected graph -- Polytope -- Facets -- Separation -- Branch-and-Cut; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2017.03.007
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A Survivable network design problem is considered from a polyhedral point of view. An integer programming formulation is presented. Valid inequalities and the facial aspects of the polytope are studied. Separation procedures and reduction operations are proposed and a Branch-and-Cut algorithm is devised. Computational results are presented and discussed. Abstract: In this paper we consider the k -node-connected subgraph problem. We propose an integer linear programming formulation for the problem and investigate the associated polytope. We introduce further classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results.