Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem

Abstract : In this article, we study the k-edge-connected L-hop-constrained network design problem. Given a weighted graph G = (V,E), a set D of pairs of nodes, two integers L ≥ 2 and k ≥ 2, the problem consists in finding a minimum weight subgraph of G containing at least k edge-disjoint paths of length at most L between every pair {s, t } ∈ D. We consider the problem in the case where L = 2, 3 and |D| ≥ 2. We first discuss integer programming formulations introduced in the literature. Then, we introduce new integer programming formulations for the problem that are based on the transformation of the initial undirected graph into directed layered graphs. We present a theoretical comparison of these formulations in terms of LP-bound. Finally, these formulations are tested using CPLEX and compared in a computational study for k = 3, 4, 5.
Type de document :
Article dans une revue
Networks, Wiley, 2016, 67 (2), 〈10.1002/net.21667〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01281958
Contributeur : Pierre Pesneau <>
Soumis le : jeudi 3 mars 2016 - 09:58:56
Dernière modification le : mercredi 6 juin 2018 - 01:07:40

Identifiants

Collections

Citation

I. Diarrassouba, V. Gabrel, A. R. Mahjoub, L. Gouveia, Pierre Pesneau. Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem. Networks, Wiley, 2016, 67 (2), 〈10.1002/net.21667〉. 〈hal-01281958〉

Partager

Métriques

Consultations de la notice

184