Thumbnail - Request a copy

The survivable k-node-connected network design problem: Valid inequalities and Branch-and-Cut

Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017), The survivable k-node-connected network design problem: Valid inequalities and Branch-and-Cut, Computers and Industrial Engineering, 112, p. 690-705. 10.1016/j.cie.2017.03.007

Type
Article accepté pour publication ou publié
Date
2017
Journal name
Computers and Industrial Engineering
Volume
112
Pages
690-705
Publication identifier
Metadata
Show full item record
Author(s)
Mahjoub, Meriem
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Diarrassouba, Ibrahima
Laboratoire de Mathématiques Appliquées du Havre [LMAH]
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Taktak, Raouia
Institut Supérieur d'Informatique et de Multimédia de Sfax [ISIMS]
Abstract (EN)
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.
Subjects / Keywords
k-node-connected graph; Polytope; Facets; Separation; Branch-and-Cut