Two node‐disjoint 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 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 in the design of survivable telecommunication 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, and propose a Branch‐and‐Cut algorithm for the problem when L  = 3, as well as some computational results. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(4), 316–337 2016