Show simple item record

dc.contributor.authorPesneau, Pierre
dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorLabbé, Martine
dc.contributor.authorHuygens, David
dc.date.accessioned2010-04-06T11:49:42Z
dc.date.available2010-04-06T11:49:42Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3839
dc.language.isoenen
dc.subjectnetwork designen
dc.subjectedge connectivityen
dc.subjecthop-constraintsen
dc.subjectNP-hardnessen
dc.subjectvalid inequalitiesen
dc.subjectfacetsen
dc.subjectbranch-and-cuten
dc.subject.ddc003en
dc.titleThe Two-Edge Connected Hop-Constrained Network Design Problem : Valid Inequalities and Branch-and-Cuten
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis 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.en
dc.relation.isversionofjnlnameNetworks
dc.relation.isversionofjnlvol49en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2007
dc.relation.isversionofjnlpages116-133en
dc.relation.isversionofdoihttp://dx.doi.org/10.1002/net.20146en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherWileyen
dc.subject.ddclabelRecherche opérationnelleen


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