Two Node-Disjoint 3-Hop-Constrained Survivable Network Design and Polyhedra

Given a weighted undirected graph G with a set of pairs of terminals { s i , t i } , i = 1 , … , d , and an integer L ⩾ 2 , the two node-disjoint hop-constrained survivable network design problem (TNHNDP) is to find a minimum weight subgraph of G such that between every s i and t i there exist at least two node-disjoint paths of length at most L. This problem has applications to the design of survivable telecommunications networks with QoS-constraints. We discuss this problem from a polyhedral point of view. We present several classes of valid inequalities along with necessary and/or sufficient conditions for these inequalities to be facet defining. We also discuss separation routines for these classes of inequalities. Using this, we propose a Branch-and-Cut algorithm for the problem when L = 3 , and present some computational results.