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.
Article
View Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Problems