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, Juan Chen

*此作品的通讯作者

科研成果: 期刊稿件文章同行评审

7 引用 (Scopus)

摘要

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.

源语言英语
页(从-至)73-87
页数15
期刊European Journal of Operational Research
311
1
DOI
出版状态已出版 - 16 11月 2023

指纹

探究 'Efficient presolving methods for solving maximal covering and partial set covering location problems' 的科研主题。它们共同构成独一无二的指纹。

引用此