In this paper, we study the hop-constrained survivable network design problem with reliable edges. Given a graph with non-negative edge weights and node pairs Q, the hop-constrained survivable network design problem consists of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. In this paper, we propose and study the hop-constrained survivable network design problem with so-called reliable edges where in addition, we consider a subset of edges that are not subject to failure. We study two variants (a static problem where the reliability of edges is given, and an upgrading problem where edges can be upgraded to the reliable status at a given cost). We adapt for the two variants an extended formulation proposed in Botton et al (2011) for the case without reliable edges. As before, due to the huge number of variables and constraints included in the extended formulations, we use Benders decomposition to accelerate the solving process. We develop an exact branch-and-cut algorithm and a fix-and-branch heuristic. Our computational results indicate that these two variants appear to be more difficult to solve than the original problem (without reliable edges). We conclude with an economical analysis which evaluates the incentive of using reliable edges in the network
Article
View On the hop-constrained survivable network design problem with reliable edges