• 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

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), Two-edge connected subgraph with bounded rings problem: Polyhedral results and Branch-and-Cut, Mathematical Programming, 105, 1, p. 85-111. http://dx.doi.org/10.1007/s10107-005-0576-5

Type
Article accepté pour publication ou publié
Date
2006
Journal name
Mathematical Programming
Volume
105
Number
1
Publisher
Springer
Pages
85-111
Publication identifier
http://dx.doi.org/10.1007/s10107-005-0576-5
Metadata
Show full item record
Author(s)
Pesneau, Pierre

Mahjoub, Ali Ridha

McCormick, S. Thomas

Fortz, bernard
Abstract (EN)
We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.
Subjects / Keywords
Network models, deterministic; Combinatorial optimization; Polyhedral combinatorics, branch-and-bound, branch-and-cut

Related items

Showing items related by title and author.

  • Thumbnail
    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) Article accepté pour publication ou publié
  • Thumbnail
    The k-node connected subgraph problem: Polyhedral analysis and Branch-and-Cut 
    Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
  • Thumbnail
    A Branch-and-Cut algorithm for the k-edge connected subgraph problem 
    Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié
  • 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
    Max Flow and Min Cut with bounded-length paths: complexity, algorithms, and approximation 
    Mahjoub, Ali Ridha; McCormick, S. Thomas (2010) Article accepté pour publication ou publié
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