Essec\Faculty\Model\Contribution {#2205
  #_index: "academ_contributions"
  #_id: "10615"
  #_source: array:26 [
    "id" => "10615"
    "slug" => "the-generalized-regenerator-location-problem"
    "yearMonth" => "2015-03"
    "year" => "2015"
    "title" => "The Generalized Regenerator Location Problem"
    "description" => "CHEN, S., LJUBIC, I. et RAGHAVAN, S. (2015). The Generalized Regenerator Location Problem. <i>INFORMS Journal on Computing</i>, 27(2), pp. 204-220."
    "authors" => array:3 [
      0 => array:3 [
        "name" => "LJUBIC Ivana"
        "bid" => "B00683004"
        "slug" => "ljubic-ivana"
      ]
      1 => array:1 [
        "name" => "CHEN Si"
      ]
      2 => array:1 [
        "name" => "RAGHAVAN S."
      ]
    ]
    "ouvrage" => ""
    "keywords" => []
    "updatedAt" => "2021-07-13 14:31:39"
    "publicationUrl" => "https://doi.org/10.1287/ijoc.2014.0621"
    "publicationInfo" => array:3 [
      "pages" => "204-220"
      "volume" => "27"
      "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" => "In an optical network a signal can only travel a maximum distance dmax before its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high, we wish to deploy as few regenerators as possible in the network, while ensuring all nodes can communicate with each other. In this paper we introduce the generalized regenerator location problem (GRLP) in which we are given a set S of nodes that corresponds to candidate locations for regenerators, and a set T of nodes that must communicate with each other. If S = T = N, we obtain the regenerator location problem (RLP), which we have studied previously and shown to be NP-complete. Our solution procedure to the RLP is based on its equivalence to the maximum leaf spanning tree problem (MLSTP). Unfortunately, this equivalence does not apply to the GRLP, nor do the procedures developed previously for the RLP. To solve the GRLP, we propose reduction procedures, two construction heuristics, and a local search procedure that we collectively refer to as a heuristic framework. We also establish a correspondence between the (node-weighted) directed Steiner forest problem and the GRLP. Using this fact, we provide several ways to derive natural and extended integer programming (IP) and mixed-integer programming (MIP) models for the GRLP and compare the strength of these models. Using the strongest model derived on the natural node selection variables we develop a branch-and-cut approach to solve the problem to optimality. The results indicate that the exact approach can easily solve instances with up to 200 nodes to optimality, whereas the heuristic framework is a high-quality approach for solving large-scale instances."
      "en" => "In an optical network a signal can only travel a maximum distance dmax before its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high, we wish to deploy as few regenerators as possible in the network, while ensuring all nodes can communicate with each other. In this paper we introduce the generalized regenerator location problem (GRLP) in which we are given a set S of nodes that corresponds to candidate locations for regenerators, and a set T of nodes that must communicate with each other. If S = T = N, we obtain the regenerator location problem (RLP), which we have studied previously and shown to be NP-complete. Our solution procedure to the RLP is based on its equivalence to the maximum leaf spanning tree problem (MLSTP). Unfortunately, this equivalence does not apply to the GRLP, nor do the procedures developed previously for the RLP. To solve the GRLP, we propose reduction procedures, two construction heuristics, and a local search procedure that we collectively refer to as a heuristic framework. We also establish a correspondence between the (node-weighted) directed Steiner forest problem and the GRLP. Using this fact, we provide several ways to derive natural and extended integer programming (IP) and mixed-integer programming (MIP) models for the GRLP and compare the strength of these models. Using the strongest model derived on the natural node selection variables we develop a branch-and-cut approach to solve the problem to optimality. The results indicate that the exact approach can easily solve instances with up to 200 nodes to optimality, whereas the heuristic framework is a high-quality approach for solving large-scale instances."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d’Information, Sciences de la Décision et Statistiques"
      "en" => "Information Systems, Decision Sciences and Statistics"
    ]
    "indexedAt" => "2024-04-30T14:22:00.000Z"
    "docTitle" => "The Generalized Regenerator Location Problem"
    "docSurtitle" => "Articles"
    "authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, CHEN Si, RAGHAVAN S."
    "docDescription" => "<span class="document-property-authors">LJUBIC Ivana, CHEN Si, RAGHAVAN S.</span><br><span class="document-property-authors_fields">Systèmes d’Information, Sciences de la Décision et Statistiques</span> | <span class="document-property-year">2015</span>"
    "keywordList" => ""
    "docPreview" => "<b>The Generalized Regenerator Location Problem</b><br><span>2015-03 | Articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://doi.org/10.1287/ijoc.2014.0621" target="_blank">The Generalized Regenerator Location Problem</a>"
  ]
  +lang: "fr"
  +"_type": "_doc"
  +"_score": 7.9894094
  +"parent": null
}