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.

中文翻译：

---

广义最大覆盖位置问题的预解析和切割平面

本文考虑了广义最大覆盖位置问题 （GMCLP），该问题建立了固定数量的设施点，以最大化覆盖客户的加权和，从而允许客户权重为正或负。由于需要大量线性约束来对候选设施点位置和客户之间的覆盖关系进行建模，尤其是线性规划 （LP） 松弛效果不佳，因此 GMCLP 极难通过最先进的混合整数规划 （MIP） 求解器进行求解。为了提高基于 MIP 的 GMCLP 求解方法的计算性能，我们提出了定制的预解析和切割平面技术，即同构聚合、优势减少和双客户不等式。同构聚集和显性减少不仅可以减小问题大小，还可以加强 GMCLP 的 MIP 公式的 LP 松弛。两个客户不等式可以嵌入到分支和切割框架中，以进一步加强 MIP 公式的 LP 动态松弛。通过广泛的计算实验，我们表明所有提出的三种技术都可以显着提高 MIP 求解器求解 GMCLP 的能力。特别是，对于文献中具有相同客户数量和候选设施位置的 40 个实例的测试平台，所提出的技术使我们能够为 13 个以前未解决的基准实例提供最佳解决方案;对于客户数量远大于候选设施点位置数量的 336 个实例的测试平台，所提出的技术可以将其中大多数实例从棘手变为易于解决。