• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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

Type
Article accepté pour publication ou publié
Date
2019
Journal name
European Journal of Operational Research
Volume
275
Number
3
Publisher
Elsevier
Pages
882-896
Publication identifier
10.1016/j.ejor.2018.12.021
Metadata
Show full item record
Author(s)
Cordeau, Jean-François
autre
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ljubić, Ivana
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 / Keywords
Combinatorial optimization; Location problems; Covering; Benders decomposition; Branch-and-cut algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem 
    Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2017) Article accepté pour publication ou publié
  • Thumbnail
    ILP and CP Formulations for the Lazy Bureaucrat Problem 
    Furini, Fabio; Ljubić, Ivana; Sinnl, Markus (2015) Communication / Conférence
  • Thumbnail
    A new branch-and-bound algorithm for the maximum edge-weighted clique problem 
    San Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana (2019) Article accepté pour publication ou publié
  • Thumbnail
    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é
  • Thumbnail
    The maximum clique interdiction problem 
    Furini, Fabio; Ljubić, Ivana; Martin, Sébastien; San Segundo, Pablo (2019) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo