Essec\Faculty\Model\Contribution {#2233 ▼
#_index: "academ_contributions"
#_id: "10491"
#_source: array:26 [
"id" => "10491"
"slug" => "10491-enhanced-formulations-and-branch-and-cut-for-the-two-level-network-design-problem-with-transition-facilities 
10491-enhanced-formulations-and-branch-and-cut-for-the-two-level-network-design-problem-with-transit "
"yearMonth" => "2013-03"
"year" => "2013"
"title" => "Enhanced Formulations and Branch-and-Cut for the Two Level Network Design Problem with Transition Facilities Enhanced Formulations and Branch-and-Cut for the Two Level Network Design Problem with Transition Fa "
"description" => "GOLLOWITZER, S., GOUVEIA, L. et LJUBIC, I. (2013). Enhanced Formulations and Branch-and-Cut for the Two Level Network Design Problem with Transition Facilities. <i>European Journal of Operational Research</i>, 225(2), pp. 211-222. GOLLOWITZER, S., GOUVEIA, L. et LJUBIC, I. (2013). Enhanced Formulations and Branch-and-Cut for the "
"authors" => array:3 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "GOLLOWITZER Stefan"
]
2 => array:1 [
"name" => "GOUVEIA Luis"
]
]
"ouvrage" => ""
"keywords" => []
"updatedAt" => "2021-07-13 14:31:36"
"publicationUrl" => "https://www.researchgate.net/publication/257196446_Enhanced_formulations_and_branch-and-cut_for_the_two_level_network_design_problem_with_transition_facilities https://www.researchgate.net/publication/257196446_Enhanced_formulations_and_branch-and-cut_for_the_ "
"publicationInfo" => array:3 [
"pages" => "211-222"
"volume" => "225"
"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" => "We consider a new combinatorial optimization problem that combines network design and facility location aspects. Given a graph with two types of customers and two technologies that can be installed on the edges, the objective is to find a minimum cost subtree connecting all customers while the primary customers are served by a primary subtree that is embedded into the secondary subtree. In addition, besides fixed link installation costs, facility opening costs, associated to each node where primary and secondary subtree connect, have to be paid. The problem is called the Two Level Network Design Problem with Transition Facilities (TLNDF).We first model the problem on an extended graph where an additional set of arcs corresponds to the installation of node facilities and propose a cut set based model for the TLNDF that is defined on this extended graph. We present several theoretical results relating families of cut set inequalities on the extended graph with subfamilies of cut set inequalities on the original graph. We then show how a standard multi-commodity flow model defined on the original graph can be strengthened using disaggregation “by technology”. We prove that the disaggregated compact formulation on the original graph provides the same lower bound as the cut set formulation on the extended graph.We develop a branch-and-cut algorithm for solving the TLNDF. The performance of this algorithm is improved by separating subfamilies of cut set inequalities on the original graph. Our computational study confirms the efficiency and applicability of the new approach. We consider a new combinatorial optimization problem that combines network design and facility locat "
"en" => "We consider a new combinatorial optimization problem that combines network design and facility location aspects. Given a graph with two types of customers and two technologies that can be installed on the edges, the objective is to find a minimum cost subtree connecting all customers while the primary customers are served by a primary subtree that is embedded into the secondary subtree. In addition, besides fixed link installation costs, facility opening costs, associated to each node where primary and secondary subtree connect, have to be paid. The problem is called the Two Level Network Design Problem with Transition Facilities (TLNDF).We first model the problem on an extended graph where an additional set of arcs corresponds to the installation of node facilities and propose a cut set based model for the TLNDF that is defined on this extended graph. We present several theoretical results relating families of cut set inequalities on the extended graph with subfamilies of cut set inequalities on the original graph. We then show how a standard multi-commodity flow model defined on the original graph can be strengthened using disaggregation “by technology”. We prove that the disaggregated compact formulation on the original graph provides the same lower bound as the cut set formulation on the extended graph.We develop a branch-and-cut algorithm for solving the TLNDF. The performance of this algorithm is improved by separating subfamilies of cut set inequalities on the original graph. Our computational study confirms the efficiency and applicability of the new approach. We consider a new combinatorial optimization problem that combines network design and facility locat "
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2025-04-02T12:21:45.000Z"
"docTitle" => "Enhanced Formulations and Branch-and-Cut for the Two Level Network Design Problem with Transition Facilities Enhanced Formulations and Branch-and-Cut for the Two Level Network Design Problem with Transition Fa "
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, GOLLOWITZER Stefan, GOUVEIA Luis"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, GOLLOWITZER Stefan, GOUVEIA Luis</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2013</span> <span class="document-property-authors">LJUBIC Ivana, GOLLOWITZER Stefan, GOUVEIA Luis</span><br><sp "
"keywordList" => ""
"docPreview" => "<b>Enhanced Formulations and Branch-and-Cut for the Two Level Network Design Problem with Transition Facilities</b><br><span>2013-03 | Articles </span> <b>Enhanced Formulations and Branch-and-Cut for the Two Level Network Design Problem with Transition "
"docType" => "research"
"publicationLink" => "<a href="https://www.researchgate.net/publication/257196446_Enhanced_formulations_and_branch-and-cut_for_the_two_level_network_design_problem_with_transition_facilities" target="_blank">Enhanced Formulations and Branch-and-Cut for the Two Level Network Design Problem with Transition Facilities</a> <a href="https://www.researchgate.net/publication/257196446_Enhanced_formulations_and_branch-and-cut "
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.784652
+"parent": null
}
