• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2002
Journal name
Operations Research Letters
Volume
30
Number
4
Publisher
Elsevier
Pages
265-268
Publication identifier
http://dx.doi.org/10.1016/S0167-6377(02)00182-7
Metadata
Show full item record
Author(s)
Kerivin, Hervé
Mahjoub, Ali Ridha
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

Related items

Showing items related by title and author.

  • Thumbnail
    On the Polytope of the (1,2)-Survivable Network Design Problem 
    Mahjoub, Ali Ridha; Kerivin, Hervé; Didi Biha, Mohamed (2008) Article accepté pour publication ou publié
  • Thumbnail
    Design of Survivable Networks: A survey 
    Kerivin, Hervé; Mahjoub, Ali Ridha (2005) Article accepté pour publication ou publié
  • Thumbnail
    (1,2)-Survivable Networks: Facets and Branch&Cut 
    Kerivin, Hervé; Mahjoub, Ali Ridha; Nocq, Charles (2004) Chapitre d'ouvrage
  • Thumbnail
    The survivable k-node-connected network design problem: Valid inequalities and Branch-and-Cut 
    Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié
  • Thumbnail
    The multilayer capacitated survivable IP network design problem: valid inequalities and branch-and-cut 
    Fouilhoux, Pierre; Klopkenstein, Olivier; Mahjoub, Ali Ridha; Borne, S. (2009) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo