Optimization Online


Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Problems

Jean-françois Cordeau(jean-francois.cordeau***at***hec.ca)
Fabio Furini(fabio.furini82***at***gmail.com)
Ivana Ljubic(ivana.ljubic***at***essec.edu)

Abstract: Covering problems constitute an important family of facility location problems. This paper intro- duces a new exact algorithm for two important members of this family: i) the maximal covering location problem, which requires finding a subset of facilities that maximizes the amount of demand covered while respecting a budget constraint on the cost of the facilities; and ii) the partial set covering location problem, which minimizes the cost of the open facilities while forcing a certain amount of demand to be covered. We study an effective decomposition approach to the two problems based on the branch-and-Benders-cut reformulation. We also report the results of a series of computational experiments demonstrating that, thanks to this decomposition techniques, optimal solutions can be found very quickly, even for benchmark instances involving up to twenty million demand points.

Keywords: Combinatorial Optimization, Location Problems, Covering, Benders Decomposition, Branch-and-Cut

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 06/19/2018
Entry Accepted: 06/19/2018
Entry Last Modified: 06/19/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society