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
2017Journal name
Computers and Industrial EngineeringVolume
112Pages
690-705
Publication identifier
Metadata
Show full item recordAuthor(s)
Mahjoub, MeriemLaboratoire 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-CutRelated items
Showing items related by title and author.
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
-
Fouilhoux, Pierre; Klopkenstein, Olivier; Mahjoub, Ali Ridha; Borne, S. (2009) Communication / Conférence
-
Pesneau, Pierre; Mahjoub, Ali Ridha; Labbé, Martine; Huygens, David (2007) Article accepté pour publication ou publié
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Yaman, Hande (2016) Article accepté pour publication ou publié
-
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper