Separation of partition inequalities for the (1,2)-survivable network design problem
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
2002Journal name
Operations Research LettersVolume
30Number
4Publisher
Elsevier
Pages
265-268
Publication identifier
Metadata
Show full item recordAbstract (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 networkRelated items
Showing items related by title and author.
-
Mahjoub, Ali Ridha; Kerivin, Hervé; Didi Biha, Mohamed (2008) Article accepté pour publication ou publié
-
Kerivin, Hervé; Mahjoub, Ali Ridha (2005) Article accepté pour publication ou publié
-
Kerivin, Hervé; Mahjoub, Ali Ridha; Nocq, Charles (2004) Chapitre d'ouvrage
-
Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié
-
Fouilhoux, Pierre; Klopkenstein, Olivier; Mahjoub, Ali Ridha; Borne, S. (2009) Communication / Conférence