Back to Search
Start Over
Hop-Level Flow Formulation for the Hop Constrained Survivable Network Design Problem
- Source :
- Network Optimization, INOC 2011, INOC 2011, Jun 2011, Hambourg, Germany. pp.176-181, ⟨10.1007/978-3-642-21527-8_23⟩, Lecture Notes in Computer Science ISBN: 9783642215261, INOC
- Publication Year :
- 2011
- Publisher :
- HAL CCSD, 2011.
-
Abstract
- International audience; The HSNDP consists in finding a minimum cost subgraph containing K edge-disjoint paths with length at most H joining each pair of vertices in a given demand set. The only formulation found in the literature that is valid for any K and any H is based on multi-commodity flows over suitable layered graphs (Hop-MCF) and has typical integrality gaps in the range of 5% to 25%. We propose a new formulation called Hop-Level-MCF (in this short paper only for the rooted demands case), having about H times more variables and constraints than Hop-MCF, but being significantly stronger. Typical gaps for rooted instances are between 0% and 6%. Some instances from the literature are solved for the first time.
- Subjects :
- 021103 operations research
Flow
Short paper
0211 other engineering and technologies
02 engineering and technology
Steiner tree problem
Hop (networking)
Combinatorics
Network planning and design
symbols.namesake
Survivable Network
Demand set
0202 electrical engineering, electronic engineering, information engineering
symbols
020201 artificial intelligence & image processing
[INFO]Computer Science [cs]
Mathematics
Hop-constraint
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-642-21526-1
- ISBNs :
- 9783642215261
- Database :
- OpenAIRE
- Journal :
- Network Optimization, INOC 2011, INOC 2011, Jun 2011, Hambourg, Germany. pp.176-181, ⟨10.1007/978-3-642-21527-8_23⟩, Lecture Notes in Computer Science ISBN: 9783642215261, INOC
- Accession number :
- edsair.doi.dedup.....1622f4f32f74db17937e86a0461debdd