• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
Date
2019
Dewey
Recherche opérationnelle
Sujet
Combinatorial optimization; Location problems; Covering; Benders decomposition; Branch-and-cut algorithms
Journal issue
European Journal of Operational Research
Volume
275
Number
3
Publication date
06-2019
Article pages
882-896
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.ejor.2018.12.021
URI
https://basepub.dauphine.fr/handle/123456789/18967
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Cordeau, Jean-François
115536 autre
Furini, Fabio
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ljubić, Ivana
24359 ESSEC Business School
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.