• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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
  • LAMSADE : Publications
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.