• 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

Distance transformation for network design problems

Thumbnail
View/Open
Distance_Transformation.pdf (800.9Kb)
Date
2019
Dewey
Informatique générale
Sujet
Extended Formulations; Network Design; Benders decomposition
Journal issue
SIAM Journal on Optimization
Volume
29
Number
2
Publication date
2019
Article pages
1687-1713
Publisher
SIAM - Society for Industrial and Applied Mathematics
DOI
http://dx.doi.org/10.1137/16M1108261
URI
https://basepub.dauphine.fr/handle/123456789/20054
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Mahjoub, Ali Ridha
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Poss, Michael
181 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Simonetti, Luidi
263498 Federal University of Rio de Janeiro
Uchoa, Eduardo
115536 autre
Type
Article accepté pour publication ou publié
Abstract (EN)
We propose a new generic way to construct extended formulations for a large class of network design problems with given connectivity requirements. The approach is based on a graph transformation that maps any graph into a layered graph according to a given distance function. The original connectivity requirements are in turn transformed into equivalent connectivity requirements in the layered graph. The mapping is extended to the graphs induced by fractional vectors through an extended linear integer programming formulation. While graphs induced by binary vectors are mapped to isomorphic layered graphs, those induced by fractional vectors are mapped to a set of graphs having worse connectivity properties. Hence, the connectivity requirements in the layered graph may cut off fractional vectors that were feasible for the problem formulated in the original graph. Experiments over instances of the Steiner forest and hop-constrained survivable network design problems show that significant gap reductions compared with state-of-the art formulations can be obtained.

  • 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.