The two‐edge connected hop‐constrained network design problem: Valid inequalities and branch‐and‐cut

This article deals with the Two‐edge connected Hop‐constrained Network Design Problem (or THNDP for short). Given a weighted graphG= (N,E), an integerL≥ 2, and a subset of pairs of nodesD, the problem consists of finding the minimum cost subgraph inGcontaining at least two edge‐disjoint paths of at mostLhops between all the pairs inD. First, we show that the THNDP is stronglyNP‐hard even when the demands inDare rooted at some nodesand the costs are unitary. However, if the graph is complete, we prove that the problem in this case can be solved in polynomial time. We give an integer programming formulation of the problem in the space of the design variables whenL= 2, 3. Then we study the associated polytope. In particular, we consider the case where all the pairs of nodes ofDare rooted at a nodes. We give several classes of valid inequalities along with necessary and/or sufficient conditions for these inequalities to be facet defining. We also derive separation routines for these inequalities. We finally develop a branch‐and‐cut algorithm based on these results and discuss some computational results forL= 2, 3.