Abstract (EN)

Given a graph G=(V,E) with edge costs and an integer vector Image associated with the nodes of V, the survivable network design problem is to find a minimum cost subgraph of G such that between every pair of nodes s,t of V, there are at least min{r(s),r(t)} edge-disjoint paths. In this paper we consider that problem when rset membership, variant{1,2}V. This case is of particular interest to the telecommunication industry. We show that the separation problem for the so-called partition inequalities reduces to minimizing a submodular function. This yields a polynomial time separation algorithm for these inequalities in that case.