Presolving and cutting planes for the generalized maximal covering location problem
Wei Lv,
Cheng-Yang Yu,
Jie Liang,
Wei-Kun Chen and
Yu-Hong Dai
European Journal of Operational Research, 2025, vol. 327, issue 2, 394-406
Abstract:
This paper considers the generalized maximal covering location problem (GMCLP) which establishes a fixed number of facilities to maximize the weighted sum of the covered customers, allowing customer weights to be positive or negative. Due to the huge number of linear constraints to model the covering relations between the candidate facility locations and customers, and particularly the poor linear programming (LP) relaxation, the GMCLP is extremely difficult to solve by state-of-the-art mixed integer programming (MIP) solvers. To improve the computational performance of MIP-based approaches for solving GMCLPs, we propose customized presolving and cutting plane techniques, which are isomorphic aggregation, dominance reduction, and two-customer inequalities. The isomorphic aggregation and dominance reduction can not only reduce the problem size but also strengthen the LP relaxation of the MIP formulation of the GMCLP. The two-customer inequalities can be embedded into a branch-and-cut framework to further strengthen the LP relaxation of the MIP formulation on the fly. By extensive computational experiments, we show that all three proposed techniques can substantially improve the capability of MIP solvers in solving GMCLPs. In particular, for a testbed of 40 instances with identical numbers of customers and candidate facility locations in the literature, the proposed techniques enable us to provide optimal solutions for 13 previously unsolved benchmark instances; for a testbed of 336 instances where the number of customers is much larger than the number of candidate facility locations, the proposed techniques can turn most of them from intractable to easily solvable.
Keywords: Location; Presolving; Cutting planes; Maximal covering location problem; Negative weights (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:
Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725003856
Full text for ScienceDirect subscribers only
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:327:y:2025:i:2:p:394-406
DOI: 10.1016/j.ejor.2025.05.017
Access Statistics for this article
European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati
More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().