Show simple item record

hal.structure.identifier
dc.contributor.authorPesneau, Pierre
HAL ID: 739311
*
hal.structure.identifier
dc.contributor.authorMahjoub, Ali Ridha*
hal.structure.identifier
dc.contributor.authorMcCormick, S. Thomas*
hal.structure.identifier
dc.contributor.authorFortz, bernard*
dc.date.accessioned2009-09-21T09:54:03Z
dc.date.available2009-09-21T09:54:03Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/1809
dc.language.isoenen
dc.subjectNetwork models, deterministicen
dc.subjectCombinatorial optimizationen
dc.subjectPolyhedral combinatorics, branch-and-bound, branch-and-cuten
dc.subject.ddc519en
dc.titleTwo-edge connected subgraph with bounded rings problem: Polyhedral results and Branch-and-Cuten
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherSauder School of Business, University of British Columbia;Canada
dc.contributor.editoruniversityotherInstitut d'Administration et de Gestion, Université Catholique de Louvain;Belgique
dc.contributor.editoruniversityotherLIMOS CNRS, Université Blaise Pascal, Clermont-Ferrand,;France
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameMathematical Programming
dc.relation.isversionofjnlvol105en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2006-01
dc.relation.isversionofjnlpages85-111en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s10107-005-0576-5en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record