DIARRASSOUBA, Ibrahima; GABREL, V.; MAHJOUB, A. R.; GOUVEIA, L.; PESNEAU, Pierre

doi:10.1002/net.21667

Metadatos

Mostrar el registro completo del ítem

Licencia de uso del documento

DIARRASSOUBA, Ibrahima
Laboratoire de Mathématiques Appliquées du Havre [LMAH]

GABREL, V.
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]

Idioma

Article de revue

Este ítem está publicado en

Networks. 2016-03, vol. 67, n° 2, p. pp. 148-169

Wiley

Resumen en inglés

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.< Leer menos

Metadatos

Compartir este ítem

Licencia de uso del documento

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

Idioma

Este ítem está publicado en

Resumen en inglés

URI

DOI

Orígen

Centros de investigación