Essec\Faculty\Model\Contribution {#2216
  #_index: "academ_contributions"
  #_id: "10405"
  #_source: array:26 [
    "id" => "10405"
    "slug" => "orientation-based-models-for-012-survivable-network-design-theory-and-practice"
    "yearMonth" => "2010-07"
    "year" => "2010"
    "title" => "Orientation-based models for {0,1,2}-survivable network design: theory and practice"
    "description" => "CHIMANI, M., KANDYBA, M., LJUBIC, I. et MUTZEL, P. (2010). Orientation-based models for {0,1,2}-survivable network design: theory and practice. <i>Mathematical Programming</i>, 124(1), pp. 413-440."
    "authors" => array:4 [
      0 => array:3 [
        "name" => "LJUBIC Ivana"
        "bid" => "B00683004"
        "slug" => "ljubic-ivana"
      ]
      1 => array:1 [
        "name" => "CHIMANI Markus"
      ]
      2 => array:1 [
        "name" => "KANDYBA Maria"
      ]
      3 => array:1 [
        "name" => "MUTZEL Petra"
      ]
    ]
    "ouvrage" => ""
    "keywords" => []
    "updatedAt" => "2021-07-13 14:31:34"
    "publicationUrl" => "https://www.researchgate.net/publication/225149430_Orientation-based_models_for_012-survivable_network_design_Theory_and_practice"
    "publicationInfo" => array:3 [
      "pages" => "413-440"
      "volume" => "124"
      "number" => "1"
    ]
    "type" => array:2 [
      "fr" => "Articles"
      "en" => "Journal articles"
    ]
    "support_type" => array:2 [
      "fr" => "Revue scientifique"
      "en" => "Scientific journal"
    ]
    "countries" => array:2 [
      "fr" => null
      "en" => null
    ]
    "abstract" => array:2 [
      "fr" => "We consider {0,1,2}-Survivable Network Design problems with node-connectivity constraints. In the most prominent variant, we are given an edge-weighted graph and two customer sets ℛ1 and ℛ2 ; we ask for a minimum cost subgraph that connects all customers, and guarantees two-node-connectivity for the ℛ2 customers. We also consider an alternative of this problem, in which 2-node-connectivity is only required w.r.t. a certain root node, and its prize-collecting variant. The central result of this paper is a novel graph-theoretical characterization of 2-node-connected graphs via orientation properties. This allows us to derive two classes of ILP formulations based on directed graphs, one using multi-commodity flow and one using cut-inequalities. We prove the theoretical advantages of these directed models compared to the previously known ILP approaches. We show that our two concepts are equivalent from the polyhedral point of view. On the other hand, our experimental study shows that the cut formulation is much more powerful in practice. Moreover, we propose a collection of benchmark instances that can be used for further research on this topic."
      "en" => "We consider {0,1,2}-Survivable Network Design problems with node-connectivity constraints. In the most prominent variant, we are given an edge-weighted graph and two customer sets ℛ1 and ℛ2 ; we ask for a minimum cost subgraph that connects all customers, and guarantees two-node-connectivity for the ℛ2 customers. We also consider an alternative of this problem, in which 2-node-connectivity is only required w.r.t. a certain root node, and its prize-collecting variant. The central result of this paper is a novel graph-theoretical characterization of 2-node-connected graphs via orientation properties. This allows us to derive two classes of ILP formulations based on directed graphs, one using multi-commodity flow and one using cut-inequalities. We prove the theoretical advantages of these directed models compared to the previously known ILP approaches. We show that our two concepts are equivalent from the polyhedral point of view. On the other hand, our experimental study shows that the cut formulation is much more powerful in practice. Moreover, we propose a collection of benchmark instances that can be used for further research on this topic."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2024-12-21T13:21:43.000Z"
    "docTitle" => "Orientation-based models for {0,1,2}-survivable network design: theory and practice"
    "docSurtitle" => "Journal articles"
    "authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, CHIMANI Markus, KANDYBA Maria, MUTZEL Petra"
    "docDescription" => "<span class="document-property-authors">LJUBIC Ivana, CHIMANI Markus, KANDYBA Maria, MUTZEL Petra</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2010</span>"
    "keywordList" => ""
    "docPreview" => "<b>Orientation-based models for {0,1,2}-survivable network design: theory and practice</b><br><span>2010-07 | Journal articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://www.researchgate.net/publication/225149430_Orientation-based_models_for_012-survivable_network_design_Theory_and_practice" target="_blank">Orientation-based models for {0,1,2}-survivable network design: theory and practice</a>"
  ]
  +lang: "en"
  +"_type": "_doc"
  +"_score": 9.076504
  +"parent": null
}