Optimization algorithms for the k edge-connected L-hop-constrained network design problem

In this paper, 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 \ge 2\) and \(k \ge 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\}\) of D. The problem has several applications in telecommunications network design. It also has applications in reliable container transportation network design and public transportation. Even if the problem has been studied for several decades, it appears, to the best of our knowledge, that the associated polytope is not well known, even when \(L \in \{2,3\}\). In this paper, we are particularly interested in the polyhedral analysis of the problem as well as an exact solving of the problem for large-scale instances. We consider the case where \(L \in \{2,3\}\) and present two integer programming formulations introduced in Diarrassouba et al. (2016). Then, we consider the polytope associated with these formulations, and present several new classes of valid inequalities, involving the so-called design variables. We also present separation algorithms for these inequalities and devise Branch-and-Cut algorithms for solving the problem. Finally, we present an extensive computational study for \(L \in \{2,3\}\) and \(k \in \{3,4,5\}\), in which we test the efficiency of our Branch-and-Cut algorithms. We also compare the algorithm against a resolution using CPLEX Branch-and-Cut and CPLEX Benders Decomposition frameworks. The results show that our Branch-and-Cut algorithm can be competitive against these two frameworks.