Essec\Faculty\Model\Contribution {#2233
  #_index: "academ_contributions"
  #_id: "12598"
  #_source: array:26 [
    "id" => "12598"
    "slug" => "a-branch-and-cut-algorithm-for-the-edge-interdiction-clique-problem"
    "yearMonth" => "2021-10"
    "year" => "2021"
    "title" => "A branch-and-cut algorithm for the Edge Interdiction Clique Problem"
    "description" => "FURINI, F., LJUBIC, I., SAN SEGUNDO, P. et ZHAO, Y. (2021). A branch-and-cut algorithm for the Edge Interdiction Clique Problem. <i>European Journal of Operational Research</i>, 294(1), pp. 54-69."
    "authors" => array:4 [
      0 => array:3 [
        "name" => "LJUBIC Ivana"
        "bid" => "B00683004"
        "slug" => "ljubic-ivana"
      ]
      1 => array:3 [
        "name" => "ZHAO Yanlu"
        "bid" => "B00000901"
        "slug" => "alfandari-laurent"
      ]
      2 => array:1 [
        "name" => "FURINI Fabio"
      ]
      3 => array:1 [
        "name" => "SAN SEGUNDO Pablo"
      ]
    ]
    "ouvrage" => ""
    "keywords" => array:1 [
      0 => "Combinatorial optimization -Interdiction problems -Maximum clique -Most vital edges"
    ]
    "updatedAt" => "2023-01-27 01:00:40"
    "publicationUrl" => "https://doi.org/10.1016/j.ejor.2021.01.030"
    "publicationInfo" => array:3 [
      "pages" => "54-69"
      "volume" => "294"
      "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" => "Given a graph G and an interdiction budget k, the Edge Interdiction Clique Problem (EICP) asks to find a subset of at most k edges to remove from G so that the size of the maximum clique, in the interdicted graph, is minimized. The EICP belongs to the family of interdiction problems with the aim of reducing the clique number of the graph. The EICP optimal solutions, called optimal interdiction policies, determine the subset of most vital edges of a graph which are crucial for preserving its clique number. We propose a new set-covering-based Integer Linear Programming (ILP) formulation for the EICP with an exponential number of constraints, called the clique-covering inequalities. We design a new branch-and-cut algorithm which is enhanced by a tailored separation procedure and by an effective heuristic initialization phase. Thanks to the new exact algorithm, we manage to solve the EICP in several sets of instances from the literature. Extensive tests show that the new exact algorithm greatly outperforms the state-of-the-art approaches for the EICP."
      "en" => "Given a graph G and an interdiction budget k, the Edge Interdiction Clique Problem (EICP) asks to find a subset of at most k edges to remove from G so that the size of the maximum clique, in the interdicted graph, is minimized. The EICP belongs to the family of interdiction problems with the aim of reducing the clique number of the graph. The EICP optimal solutions, called optimal interdiction policies, determine the subset of most vital edges of a graph which are crucial for preserving its clique number. We propose a new set-covering-based Integer Linear Programming (ILP) formulation for the EICP with an exponential number of constraints, called the clique-covering inequalities. We design a new branch-and-cut algorithm which is enhanced by a tailored separation procedure and by an effective heuristic initialization phase. Thanks to the new exact algorithm, we manage to solve the EICP in several sets of instances from the literature. Extensive tests show that the new exact algorithm greatly outperforms the state-of-the-art approaches for the EICP."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2024-11-21T08:21:48.000Z"
    "docTitle" => "A branch-and-cut algorithm for the Edge Interdiction Clique Problem"
    "docSurtitle" => "Articles"
    "authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, <a href="/cv/alfandari-laurent">ZHAO Yanlu</a>, FURINI Fabio, SAN SEGUNDO Pablo"
    "docDescription" => "<span class="document-property-authors">LJUBIC Ivana, ZHAO Yanlu, FURINI Fabio, SAN SEGUNDO Pablo</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2021</span>"
    "keywordList" => "<a href="#">Combinatorial optimization -Interdiction problems -Maximum clique -Most vital edges</a>"
    "docPreview" => "<b>A branch-and-cut algorithm for the Edge Interdiction Clique Problem</b><br><span>2021-10 | Articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://doi.org/10.1016/j.ejor.2021.01.030" target="_blank">A branch-and-cut algorithm for the Edge Interdiction Clique Problem</a>"
  ]
  +lang: "fr"
  +"_type": "_doc"
  +"_score": 8.613594
  +"parent": null
}