On survivable network polyhedra Original Research Article

Given an undirected network image, a vector of nonnegative integers image 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 image image of image there are at least image{image} 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 image is even for all image, 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.