Hop-Level Flow Formulation for the Hop Constrained Survivable Network Design Problem
Uchoa, Eduardo; Simonetti, Luidi; Mahjoub, Ali Ridha (2012), Hop-Level Flow Formulation for the Hop Constrained Survivable Network Design Problem, in Voß, Stefan; Reiners, Torsten; Pahl, Julia, Network Optimization, Springer, p. 176-181. 10.1007/978-3-642-21527-8_23
TypeCommunication / Conférence
Conference titleINOC 2011
Book titleNetwork Optimization
Book authorVoß, Stefan; Reiners, Torsten; Pahl, Julia
Series titleLecture Notes in Computer Science
MetadataShow full item record
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)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 / KeywordsFlow; Survivable Network; Hop-constraint
Showing items related by title and author.
Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem Diarrassouba, Ibrahima; Gabrel, Virginie; Mahjoub, Ali Ridha; Gouveia, Luis; Pesneau, Pierre (2016) Article accepté pour publication ou publié