Benders decomposition for very large scale partial set covering and maximal covering location problems
Cordeau, Jean-François; Furini, Fabio; Ljubić, Ivana (2019), Benders decomposition for very large scale partial set covering and maximal covering location problems, European Journal of Operational Research, 275, 3, p. 882-896. 10.1016/j.ejor.2018.12.021
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
ESSEC Business School
Abstract (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.
Subjects / KeywordsCombinatorial optimization; Location problems; Covering; Benders decomposition; Branch-and-cut algorithms
Showing items related by title and author.
An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment Ribeiro, Celso Carneiro; Minoux, Michel; Penna, Manoel Camillo (1989) Article accepté pour publication ou publié