• 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

Two-edge connected subgraph with bounded rings problem: Polyhedral results and Branch-and-Cut

Thumbnail
Date
2006
Dewey
Probabilités et mathématiques appliquées
Sujet
Network models, deterministic; Combinatorial optimization; Polyhedral combinatorics, branch-and-bound, branch-and-cut
Journal issue
Mathematical Programming
Volume
105
Number
1
Publication date
01-2006
Article pages
85-111
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s10107-005-0576-5
URI
https://basepub.dauphine.fr/handle/123456789/1809
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Pesneau, Pierre
Mahjoub, Ali Ridha
McCormick, S. Thomas
Fortz, bernard
Type
Article accepté pour publication ou publié
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.

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