Premium
Integer programming formulations for the k ‐edge‐connected 3‐hop‐constrained network design problem
Author(s) -
Diarrassouba I.,
Gabrel V.,
Mahjoub A. R.,
Gouveia L.,
Pesneau P.
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21667
Subject(s) - integer programming , combinatorics , mathematics , disjoint sets , integer (computer science) , hop (telecommunications) , discrete mathematics , linear programming , graph , network planning and design , mathematical optimization , computer science , computer network , programming language
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. © 2015 Wiley Periodicals, Inc. NETWORKS, 67(2), 148–169 2016