Essec\Faculty\Model\Contribution {#2216
  #_index: "academ_contributions"
  #_id: "2744"
  #_source: array:26 [
    "id" => "2744"
    "slug" => "thinning-out-steiner-trees-a-node-based-model-for-uniform-edge-costs"
    "yearMonth" => "2017-06"
    "year" => "2017"
    "title" => "Thinning out Steiner Trees: A Node-Based Model for Uniform Edge Costs"
    "description" => "FISCHETTI, M., LEITNER, M., LJUBIC, I., LUIPERSBECK, M., MONACI, M. et RESCH, M. (2017). Thinning out Steiner Trees: A Node-Based Model for Uniform Edge Costs. <i>Mathematical Programming Computation</i>, 9(2), pp. 203-229."
    "authors" => array:6 [
      0 => array:3 [
        "name" => "LJUBIC Ivana"
        "bid" => "B00683004"
        "slug" => "ljubic-ivana"
      ]
      1 => array:1 [
        "name" => "FISCHETTI M."
      ]
      2 => array:1 [
        "name" => "LEITNER M."
      ]
      3 => array:1 [
        "name" => "LUIPERSBECK M."
      ]
      4 => array:1 [
        "name" => "MONACI M."
      ]
      5 => array:1 [
        "name" => "RESCH M."
      ]
    ]
    "ouvrage" => ""
    "keywords" => []
    "updatedAt" => "2021-09-24 10:33:27"
    "publicationUrl" => "https://link.springer.com/article/10.1007/s12532-016-0111-0"
    "publicationInfo" => array:3 [
      "pages" => "203-229"
      "volume" => "9"
      "number" => "2"
    ]
    "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" => "The Steiner tree problem is a challenging NP-hard problem. Many hard instances of this problem are publicly available, that are still unsolved by state-of-the-art branch-and-cut codes. A typical strategy to attack these instances is to enrich the polyhedral description of the problem, and/or to implement more and more sophisticated separation procedures and branching strategies. In this paper we investigate the opposite viewpoint, and try to make the solution method as simple as possible while working on the modeling side. Our working hypothesis is that the extreme hardness of some classes of instances mainly comes from over-modeling, and that some instances can become quite easy to solve when a simpler model is considered. In other words, we aim at “thinning out” the usual models for the sake of getting a more agile framework. In particular, we focus on a model that only involves node variables, which is rather appealing for the “uniform” cases where all edges have the same cost. In our computational study, we first show that this new model allows one to quickly produce very good (sometimes proven optimal) solutions for notoriously hard instances from the literature. In some cases, our approach takes just few seconds to prove optimality for instances never solved (even after days of computation) by the standard methods. Moreover, we report improved solutions for several SteinLib instances, including the (in)famous hypercube ones. We also demonstrate how to build a unified solver on top of the new node-based model and the previous state-of-the-art model (defined in the space of arc and node variables). The solver relies on local branching, initialization heuristics, preprocessing and local search procedures. A filtering mechanism is applied to automatically select the best algorithmic ingredients for each instance individually. The presented solver is the winner of the DIMACS Challenge on Steiner trees in most of the considered categories."
      "en" => "The Steiner tree problem is a challenging NP-hard problem. Many hard instances of this problem are publicly available, that are still unsolved by state-of-the-art branch-and-cut codes. A typical strategy to attack these instances is to enrich the polyhedral description of the problem, and/or to implement more and more sophisticated separation procedures and branching strategies. In this paper we investigate the opposite viewpoint, and try to make the solution method as simple as possible while working on the modeling side. Our working hypothesis is that the extreme hardness of some classes of instances mainly comes from over-modeling, and that some instances can become quite easy to solve when a simpler model is considered. In other words, we aim at “thinning out” the usual models for the sake of getting a more agile framework. In particular, we focus on a model that only involves node variables, which is rather appealing for the “uniform” cases where all edges have the same cost. In our computational study, we first show that this new model allows one to quickly produce very good (sometimes proven optimal) solutions for notoriously hard instances from the literature. In some cases, our approach takes just few seconds to prove optimality for instances never solved (even after days of computation) by the standard methods. Moreover, we report improved solutions for several SteinLib instances, including the (in)famous hypercube ones. We also demonstrate how to build a unified solver on top of the new node-based model and the previous state-of-the-art model (defined in the space of arc and node variables). The solver relies on local branching, initialization heuristics, preprocessing and local search procedures. A filtering mechanism is applied to automatically select the best algorithmic ingredients for each instance individually. The presented solver is the winner of the DIMACS Challenge on Steiner trees in most of the considered categories."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2024-12-03T16:21:42.000Z"
    "docTitle" => "Thinning out Steiner Trees: A Node-Based Model for Uniform Edge Costs"
    "docSurtitle" => "Journal articles"
    "authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, FISCHETTI M., LEITNER M., LUIPERSBECK M., MONACI M., RESCH M."
    "docDescription" => "<span class="document-property-authors">LJUBIC Ivana, FISCHETTI M., LEITNER M., LUIPERSBECK M., MONACI M., RESCH M.</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2017</span>"
    "keywordList" => ""
    "docPreview" => "<b>Thinning out Steiner Trees: A Node-Based Model for Uniform Edge Costs</b><br><span>2017-06 | Journal articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://link.springer.com/article/10.1007/s12532-016-0111-0" target="_blank">Thinning out Steiner Trees: A Node-Based Model for Uniform Edge Costs</a>"
  ]
  +lang: "en"
  +"_type": "_doc"
  +"_score": 9.379295
  +"parent": null
}