• 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 Two-Edge Connected Hop-Constrained Network Design Problem : Valid Inequalities and Branch-and-Cut

Thumbnail
Date
2007
Dewey
Recherche opérationnelle
Sujet
network design; edge connectivity; hop-constraints; NP-hardness; valid inequalities; facets; branch-and-cut
Journal issue
Networks
Volume
49
Number
1
Publication date
2007
Article pages
116-133
Publisher
Wiley
DOI
http://dx.doi.org/10.1002/net.20146
URI
https://basepub.dauphine.fr/handle/123456789/3839
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Pesneau, Pierre
Mahjoub, Ali Ridha
Labbé, Martine
Huygens, David
Type
Article accepté pour publication ou publié
Abstract (EN)
This article deals with the Two-edge connected Hop-constrained Network Design Problem (or THNDP for short). Given a weighted graph G = (N,E), an integer L 2, and a subset of pairs of nodes D, the problem consists of finding the minimum cost subgraph in G containing at least two edge-disjoint paths of at most L hops between all the pairs in D. First, we show that the THNDP is strongly NP-hard even when the demands in D are rooted at some node s and the costs are unitary. However, if the graph is complete, we prove that the problem in this case can be solved in polynomial time. We give an integer programming formulation of the problem in the space of the design variables when L = 2, 3. Then we study the associated polytope. In particular, we consider the case where all the pairs of nodes of D are rooted at a node s. We give several classes of valid inequalities along with necessary and/or sufficient conditions for these inequalities to be facet defining. We also derive separation routines for these inequalities. We finally develop a branch-and-cut algorithm based on these results and discuss some computational results for L = 2, 3.

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