Hop-level flow formulation for the survivable network design with hop constraints problem
Mahjoub, Ali Ridha; Simonetti, Luidi; Uchoa, Eduardo (2013), Hop-level flow formulation for the survivable network design with hop constraints problem, Networks, 61, 2, p. 171-179. 10.1002/net.21483
TypeArticle accepté pour publication ou publié
MetadataShow full item record
Author(s)Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)The hop-constrained survivable network design problem consists of 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. When all demands have a common vertex, the instance is said to be rooted. We propose a new extended formulation for the rooted case, called hop-level multicommodity flow (MCF), that can be significantly stronger than the previously known formulations, at the expense of having a larger number of variables and constraints, growing linearly with the number of edges and demands and quadratically with H. However, for the particular case where H = 2, it can be specialized into a very compact and efficient formulation. Even when H = 3, hop-level-MCF can still be quite efficient and it has solved several instances from the literature for the first time.
Subjects / Keywordsnetwork design; survivability; extended formulations
Showing items related by title and author.
Gabrel, Virginie; Mahjoub, Ali Ridha; Taktak, Raouia; Uchoa, Eduardo (2020) Article accepté pour publication ou publié
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é