Essec\Faculty\Model\Contribution {#2233
  #_index: "academ_contributions"
  #_id: "10375"
  #_source: array:26 [
    "id" => "10375"
    "slug" => "a-branch-and-cut-and-price-algorithm-for-vertex-biconnectivity-augmentation"
    "yearMonth" => "2010-10"
    "year" => "2010"
    "title" => "A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation"
    "description" => "LJUBIC, I. (2010). A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation. <i>Networks</i>, 56(3), pp. 169-182."
    "authors" => array:1 [
      0 => array:3 [
        "name" => "LJUBIC Ivana"
        "bid" => "B00683004"
        "slug" => "ljubic-ivana"
      ]
    ]
    "ouvrage" => ""
    "keywords" => []
    "updatedAt" => "2021-07-13 14:31:33"
    "publicationUrl" => "https://www.researchgate.net/publication/220209511_A_Branch-and-Cut-and-Price_Algorithm_for_Vertex-Biconnectivity_Augmentation"
    "publicationInfo" => array:3 [
      "pages" => "169-182"
      "volume" => "56"
      "number" => "3"
    ]
    "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" => "In this article, the first approach for solving the vertex-biconnectivity augmentation problem (V2AUG) to optimality is proposed. Given a spanning subgraph of an edge-weighted graph, we search for the cheapest subset of edges to augment this subgraph to make it vertex-biconnected. The problem is reduced to augmentation of the corresponding block-cut tree [Khuller and Thummella, J Algorithms 14 (1993), 214–225], and its connectivity properties are exploited to develop two minimum-cut-based ILP formulations: a directed and an undirected one. In contrast to the recently obtained result for the more general vertex-biconnected Steiner network problem [Chimani et al., Proceedings of 2nd Annual International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science, Vol. 5165, Springer, 2008, pp. 190–200.], our theoretical comparison shows that orienting the undirected graph does not help in improving the quality of lower bounds. Hence, starting from the undirected cut formulation, we develop a branch-and-cut-and-price (BCP) algorithm which represents the first exact approach to V2AUG. Our computational experiments show the practical feasibility of BCP: complete graphs with more than 400 vertices can be solved to provable optimality. Furthermore, BCP is even faster than state-of-the-art metaheuristics and approximation algorithms, for graphs up to 200 vertices. For large graphs with more than 2000 vertices, optimality gaps that are strictly below 2% are reported. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010"
      "en" => "In this article, the first approach for solving the vertex-biconnectivity augmentation problem (V2AUG) to optimality is proposed. Given a spanning subgraph of an edge-weighted graph, we search for the cheapest subset of edges to augment this subgraph to make it vertex-biconnected. The problem is reduced to augmentation of the corresponding block-cut tree [Khuller and Thummella, J Algorithms 14 (1993), 214–225], and its connectivity properties are exploited to develop two minimum-cut-based ILP formulations: a directed and an undirected one. In contrast to the recently obtained result for the more general vertex-biconnected Steiner network problem [Chimani et al., Proceedings of 2nd Annual International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science, Vol. 5165, Springer, 2008, pp. 190–200.], our theoretical comparison shows that orienting the undirected graph does not help in improving the quality of lower bounds. Hence, starting from the undirected cut formulation, we develop a branch-and-cut-and-price (BCP) algorithm which represents the first exact approach to V2AUG. Our computational experiments show the practical feasibility of BCP: complete graphs with more than 400 vertices can be solved to provable optimality. Furthermore, BCP is even faster than state-of-the-art metaheuristics and approximation algorithms, for graphs up to 200 vertices. For large graphs with more than 2000 vertices, optimality gaps that are strictly below 2% are reported. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010"
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2024-11-21T13:21:44.000Z"
    "docTitle" => "A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation"
    "docSurtitle" => "Articles"
    "authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>"
    "docDescription" => "<span class="document-property-authors">LJUBIC Ivana</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2010</span>"
    "keywordList" => ""
    "docPreview" => "<b>A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation</b><br><span>2010-10 | Articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://www.researchgate.net/publication/220209511_A_Branch-and-Cut-and-Price_Algorithm_for_Vertex-Biconnectivity_Augmentation" target="_blank">A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation</a>"
  ]
  +lang: "fr"
  +"_type": "_doc"
  +"_score": 8.769787
  +"parent": null
}