Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem
MAHJOUB, A. R.
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Voir plus >
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
MAHJOUB, A. R.
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
PESNEAU, Pierre
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Réduire
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Langue
en
Article de revue
Ce document a été publié dans
Networks. 2016-03, vol. 67, n° 2, p. pp. 148-169
Wiley
Résumé en anglais
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 ...Lire la suite >
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.< Réduire
Origine
Importé de halUnités de recherche