Efficient presolving methods for solving maximal covering and partial set covering location problems

Liang Chen, Sheng-Jie Chen, Wei-Kun Chen, Yu-Hong Dai, Tao Quan and Juan Chen

European Journal of Operational Research, 2023, vol. 311, issue 1, 73-87

Abstract: The maximal covering location problem (MCLP) and the partial set covering location problem (PSCLP) are two fundamental problems in facility location and have widespread applications in practice. The MCLP determines a subset of facilities to open to maximize the demand of covered customers subject to a budget constraint on the cost of open facilities; and the PSCLP aims to minimize the cost of open facilities while requiring a certain amount of customer demand to be covered. Both problems can be modeled as mixed integer programming (MIP) formulations. Due to the intrinsic NP-hardness nature, however, it is a great challenge to solve them to optimality by MIP solvers, especially for large-scale cases. In this paper, we present five customized presolving methods to enhance the capability of employing MIP solvers in solving the two problems. The five presolving methods are designed to reduce the sizes of the problem formulation and the search tree of the branch-and-cut procedure. For planar problems with an extremely huge number of customers under realistic types of facility coverage, we show that the number of customers in the reduced problems can be bounded above by a quadratic polynomial of the number of facilities. By extensive numerical experiments, the five presolving methods are demonstrated to be effective in accelerating the solution process of solving the MCLP and PSCLP. Moreover, they enable to solve problems with billions of customers, which is at least one order of magnitude larger than those that can be tackled by previous approaches.

Keywords: Location; Mixed integer programming; Presolving methods; Branch-and-cut (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723003417
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:311:y:2023:i:1:p:73-87

DOI: 10.1016/j.ejor.2023.04.044

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 ().