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

Thumbnail
Date
2017
Dewey
Programmation, logiciels, organisation des données
Sujet
k-node-connected graph; Polytope; Facets; Separation; Branch-and-Cut
Journal issue
Computers and Industrial Engineering
Volume
112
Publication date
10-2017
Article pages
690-705
DOI
http://dx.doi.org/10.1016/j.cie.2017.03.007
URI
https://basepub.dauphine.fr/handle/123456789/20736
Collections
Metadata
Show full item record
Author
Mahjoub, Meriem
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Diarrassouba, Ibrahima
87 Laboratoire de Mathématiques Appliquées du Havre [LMAH]
Mahjoub, Ali Ridha
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Taktak, Raouia
136703 Institut Supérieur d'Informatique et de Multimédia de Sfax [ISIMS]
Type
Article accepté pour publication ou publié
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.