On survivable network polyhedra

Given an undirected network G=(V,E), a vector of nonnegative integers r=(r(v):v∈V) associated with the nodes of G and weights on the edges of G, the survivable network design problem is to determine a minimum-weight subnetwork of G such that between every two nodes u,v of V, there are at least min{r(u),r(v)} edge-disjoint paths. In this paper we study the polytope associated with the solutions to that problem. We show that when the underlying network is series-parallel and r(v) is even for all v∈V, the polytope is completely described by the trivial constraints and the so-called cut constraints. As a consequence, we obtain a polynomial time algorithm for the survivable network design problem in that class of networks. This generalizes and unifies known results in the literature. We also obtain a linear description of the polyhedron associated with the problem in the same class of networks when the use of more than one copy of an edge is allowed.