Essec\Faculty\Model\Contribution {#2233
  #_index: "academ_contributions"
  #_id: "15268"
  #_source: array:26 [
    "id" => "15268"
    "slug" => "15268-common-flow-formulations-for-the-diameter-constrained-spanning-and-steiner-tree-problems"
    "yearMonth" => "2024-06"
    "year" => "2024"
    "title" => "Common-Flow Formulations for the Diameter Constrained Spanning and Steiner Tree Problems"
    "description" => "GOUVEIA, L., LJUBIC, I. et LEITNER, M. (2024). Common-Flow Formulations for the Diameter Constrained Spanning and Steiner Tree Problems. Dans: Teodor Gabriel Crainic, Michel Gendreau, Antonio Frangioni eds. <i>Combinatorial Optimization and Applications</i>. 1 ed. Cham: Springer Nature Switzerland, pp. 37-58."
    "authors" => array:3 [
      0 => array:3 [
        "name" => "LJUBIC Ivana"
        "bid" => "B00683004"
        "slug" => "ljubic-ivana"
      ]
      1 => array:1 [
        "name" => "Gouveia Luis"
      ]
      2 => array:1 [
        "name" => "Leitner Markus"
      ]
    ]
    "ouvrage" => "Combinatorial Optimization and Applications"
    "keywords" => array:1 [
      0 => "Combinatorial Optimization"
    ]
    "updatedAt" => "2025-10-09 11:42:44"
    "publicationUrl" => "https://doi.org/10.1007/978-3-031-57603-4_3"
    "publicationInfo" => array:3 [
      "pages" => "37-58"
      "volume" => ""
      "number" => ""
    ]
    "type" => array:2 [
      "fr" => "Chapitres"
      "en" => "Book chapters"
    ]
    "support_type" => array:2 [
      "fr" => "Editeur"
      "en" => "Publisher"
    ]
    "countries" => array:2 [
      "fr" => null
      "en" => null
    ]
    "abstract" => array:2 [
      "fr" => "We consider the diameter constrained minimum Steiner tree problem on a graph (DCStTP). Given an edge-weighted undirected graph whose set of nodes is partitioned into a set of terminal and potential Steiner nodes, the objective is to find a minimum-weight subtree that spans all terminal nodes such that the number of hops between any two terminal nodes does not exceed a given diameter D. In this work, we introduce mixed-integer linear programming models for the DCStTP based on the concept of triangles, i.e. diameter constrained Steiner trees induced by terminal subsets of size three. Starting from a formulation that models a D-hop Steiner arborescence rooted at a randomly chosen terminal node, we discuss various possibilities of realizing triangles using multi-commodity, common, or uncommon flows. We analyse the strength of these models both theoretically and empirically, and investigate how their respective Benders reformulations influence the computational performance."
      "en" => "We consider the diameter constrained minimum Steiner tree problem on a graph (DCStTP). Given an edge-weighted undirected graph whose set of nodes is partitioned into a set of terminal and potential Steiner nodes, the objective is to find a minimum-weight subtree that spans all terminal nodes such that the number of hops between any two terminal nodes does not exceed a given diameter D. In this work, we introduce mixed-integer linear programming models for the DCStTP based on the concept of triangles, i.e. diameter constrained Steiner trees induced by terminal subsets of size three. Starting from a formulation that models a D-hop Steiner arborescence rooted at a randomly chosen terminal node, we discuss various possibilities of realizing triangles using multi-commodity, common, or uncommon flows. We analyse the strength of these models both theoretically and empirically, and investigate how their respective Benders reformulations influence the computational performance."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2025-12-07T09:21:48.000Z"
    "docTitle" => "Common-Flow Formulations for the Diameter Constrained Spanning and Steiner Tree Problems"
    "docSurtitle" => "Chapitres"
    "authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, Gouveia Luis, Leitner Markus"
    "docDescription" => "<span class="document-property-authors">LJUBIC Ivana, Gouveia Luis, Leitner Markus</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2024</span>"
    "keywordList" => "<a href="#">Combinatorial Optimization</a>"
    "docPreview" => "<b>Common-Flow Formulations for the Diameter Constrained Spanning and Steiner Tree Problems</b><br><span>2024-06 | Chapitres </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://doi.org/10.1007/978-3-031-57603-4_3" target="_blank">Common-Flow Formulations for the Diameter Constrained Spanning and Steiner Tree Problems</a>"
  ]
  +lang: "fr"
  +"_score": 8.985612
  +"_ignored": array:3 [
    0 => "abstract.en.keyword"
    1 => "abstract.fr.keyword"
    2 => "description.keyword"
  ]
  +"parent": null
}