Skip to Main content Skip to Navigation
Journal articles

Benders decomposition for very large scale partial set covering and maximal covering location problems

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-02152294
Contributor : Accord Elsevier Ccsd Connect in order to contact the contributor
Submitted on : Friday, October 22, 2021 - 9:55:39 AM
Last modification on : Wednesday, November 17, 2021 - 12:27:16 PM

File

S0377221718310737.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License

Identifiers

Citation

Jean-François Cordeau, Fabio Furini, Ivana Ljubić. Benders decomposition for very large scale partial set covering and maximal covering location problems. European Journal of Operational Research, Elsevier, 2019, 275 (3), ⟨10.1016/j.ejor.2018.12.021⟩. ⟨hal-02152294⟩

Share

Metrics

Record views

95

Files downloads

13