• 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

Hop-level flow formulation for the survivable network design with hop constraints problem

Thumbnail
Date
2013
Dewey
Informatique générale
Sujet
network design; survivability; extended formulations
Journal issue
Networks
Volume
61
Number
2
Publication date
2013
Article pages
171-179
Publisher
Wiley
DOI
http://dx.doi.org/10.1002/net.21483
URI
https://basepub.dauphine.fr/handle/123456789/11430
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]
Simonetti, Luidi
Uchoa, Eduardo
Type
Article accepté pour publication ou publié
Abstract (EN)
The hop-constrained survivable network design problem consists of finding a minimum cost subgraph containing K edge-disjoint paths with length at most H joining each pair of vertices in a given demand set. When all demands have a common vertex, the instance is said to be rooted. We propose a new extended formulation for the rooted case, called hop-level multicommodity flow (MCF), that can be significantly stronger than the previously known formulations, at the expense of having a larger number of variables and constraints, growing linearly with the number of edges and demands and quadratically with H. However, for the particular case where H = 2, it can be specialized into a very compact and efficient formulation. Even when H = 3, hop-level-MCF can still be quite efficient and it has solved several instances from the literature for the first time.

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