Separation of partition inequalities for the (1,2)-survivable network design problem

Kerivin, Hervé; Mahjoub, Ali Ridha

Kerivin, Hervé; Mahjoub, Ali Ridha (2002), Separation of partition inequalities for the (1,2)-survivable network design problem, Operations Research Letters, 30, 4, p. 265-268. http://dx.doi.org/10.1016/S0167-6377(02)00182-7

Type

Article accepté pour publication ou publié

Date

2002

Journal name

Operations Research Letters

Volume

Number

Publisher

Elsevier

Pages

265-268

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.

Subjects / Keywords

Separation algorithm; Submodular function; Partition inequalities; Survivable network