Essec\Faculty\Model\Contribution {#2216
#_index: "academ_contributions"
#_id: "717"
#_source: array:26 [
"id" => "717"
"slug" => "benders-decomposition-for-very-large-scale-partial-set-covering-and-maximal-covering-location-problems"
"yearMonth" => "2019-06"
"year" => "2019"
"title" => "Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Location Problems"
"description" => "CORDEAU, J.F., FURINI, F. et LJUBIC, I. (2019). Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Location Problems. <i>European Journal of Operational Research</i>, 275(3), pp. 882-896."
"authors" => array:3 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "CORDEAU Jean-François"
]
2 => array:1 [
"name" => "FURINI Fabio"
]
]
"ouvrage" => ""
"keywords" => array:5 [
0 => "Combinatorial optimization"
1 => "Location problems"
2 => "Covering"
3 => "Benders decomposition"
4 => "Branch-and-cut algorithms"
]
"updatedAt" => "2021-09-24 10:33:27"
"publicationUrl" => "https://www.sciencedirect.com/science/article/abs/pii/S0377221718310737?via%3Dihub"
"publicationInfo" => array:3 [
"pages" => "882-896"
"volume" => "275"
"number" => "3"
]
"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" => "Covering problems constitute a fundamental family of facility location problems. This paper introduces a new exact algorithm for two important members of this family: (i) the maximal covering location problem (MCLP), which requires finding a subset of facilities that maximizes the amount of customer demand covered while respecting a budget constraint on the cost of the facilities; and (ii) the partial set covering location problem (PSCLP), which minimizes the cost of the open facilities while forcing a certain amount of customer demand to be covered. We study an effective decomposition approach to the two problems based on the branch-and-Benders-cut reformulation. Our new approach is designed for the realistic case in which the number of customers is much larger than the number of potential facility locations. We report the results of a series of computational experiments demonstrating that, thanks to this decomposition techniques, optimal solutions can be found very quickly for some benchmark instances with one hundred potential facility locations and involving up to 15 and 40 million customer demand points for the MCLP and the PSCLP, respectively."
"en" => "Covering problems constitute a fundamental family of facility location problems. This paper introduces a new exact algorithm for two important members of this family: (i) the maximal covering location problem (MCLP), which requires finding a subset of facilities that maximizes the amount of customer demand covered while respecting a budget constraint on the cost of the facilities; and (ii) the partial set covering location problem (PSCLP), which minimizes the cost of the open facilities while forcing a certain amount of customer demand to be covered. We study an effective decomposition approach to the two problems based on the branch-and-Benders-cut reformulation. Our new approach is designed for the realistic case in which the number of customers is much larger than the number of potential facility locations. We report the results of a series of computational experiments demonstrating that, thanks to this decomposition techniques, optimal solutions can be found very quickly for some benchmark instances with one hundred potential facility locations and involving up to 15 and 40 million customer demand points for the MCLP and the PSCLP, respectively."
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2024-12-13T15:21:45.000Z"
"docTitle" => "Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Location Problems"
"docSurtitle" => "Journal articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, CORDEAU Jean-François, FURINI Fabio"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, CORDEAU Jean-François, FURINI Fabio</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2019</span>"
"keywordList" => "<a href="#">Combinatorial optimization</a>, <a href="#">Location problems</a>, <a href="#">Covering</a>, <a href="#">Benders decomposition</a>, <a href="#">Branch-and-cut algorithms</a>"
"docPreview" => "<b>Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Location Problems</b><br><span>2019-06 | Journal articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://www.sciencedirect.com/science/article/abs/pii/S0377221718310737?via%3Dihub" target="_blank">Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Location Problems</a>"
]
+lang: "en"
+"_type": "_doc"
+"_score": 9.019824
+"parent": null
}