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

Pesneau, Pierre; Mahjoub, Ali Ridha; Labbé, Martine; Huygens, David (2007), The Two-Edge Connected Hop-Constrained Network Design Problem : Valid Inequalities and Branch-and-Cut, Networks, 49, 1, p. 116-133. http://dx.doi.org/10.1002/net.20146

Type
Article accepté pour publication ou publié
Date
2007
Journal name
Networks
Volume
49
Number
1
Publisher
Wiley
Pages
116-133
Publication identifier
http://dx.doi.org/10.1002/net.20146
Metadata
Show full item record
Author(s)
Pesneau, Pierre
Mahjoub, Ali Ridha
Labbé, Martine
Huygens, David
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.
Subjects / Keywords
network design; edge connectivity; hop-constraints; NP-hardness; valid inequalities; facets; branch-and-cut

Related items

Showing items related by title and author.

  • Thumbnail
    Two Edge-Disjoint Hop-Constrained Paths: Valid Inequalities and Branch-and-Cut 
    Huygens, David; Labbé, Martine; Mahjoub, Ali Ridha; Pesneau, Pierre (2005) Communication / Conférence
  • Thumbnail
    The survivable k-node-connected network design problem: Valid inequalities and Branch-and-Cut 
    Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié
  • Thumbnail
    Two-edge connected subgraph with bounded rings problem: Polyhedral results and Branch-and-Cut 
    Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) Article accepté pour publication ou publié
  • Thumbnail
    Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem 
    Diarrassouba, Ibrahima; Gabrel, Virginie; Mahjoub, Ali Ridha; Gouveia, Luis; Pesneau, Pierre (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
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