• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
10.1016/j.cie.2017.03.007
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

Related items

Showing items related by title and author.

  • Thumbnail
    The k-node connected subgraph problem: Polyhedral analysis and Branch-and-Cut 
    Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
  • Thumbnail
    The multilayer capacitated survivable IP network design problem: valid inequalities and branch-and-cut 
    Fouilhoux, Pierre; Klopkenstein, Olivier; Mahjoub, Ali Ridha; Borne, S. (2009) Communication / Conférence
  • Thumbnail
    The Two-Edge Connected Hop-Constrained Network Design Problem : Valid Inequalities and Branch-and-Cut 
    Pesneau, Pierre; Mahjoub, Ali Ridha; Labbé, Martine; Huygens, David (2007) Article accepté pour publication ou publié
  • Thumbnail
    k-node-disjoint hop-constrained survivable networks: polyhedral analysis and branch and cut 
    Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Yaman, Hande (2016) Article accepté pour publication ou publié
  • Thumbnail
    Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem 
    Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo