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.