论文标题
离散$α$ neighbor $ p $中心问题的精确解决方案方法
Exact solution approaches for the discrete $α$-neighbor $p$-center problem
论文作者
论文摘要
离散的$α$ -Neighbor $ p $ - 中心问题（D- $α$ - $ P $ CP）是经典$ p $中心问题的新兴变体，最近在文献中引起了人们的注意。在此问题中，我们为我们提供了一组离散的积分，我们需要在这些点上找到$ p $设施，以使每个设施所在的每个点之间的最大距离以及其$α$ -closeant设施的最小距离最小化。解决D- $α$ -P $ CP的文献中唯一现有的算法是近似算法和两种最近提出的启发式方法。 在这项工作中，我们为D- $α$ - $ P $ CP提供了两个整数编程公式，以及提升不平等，有效的不平等，不更改最佳目标函数值和可变修复程序的不平等现象。我们提供了理论上的结果，以迭代方式应用起重过程或可变固定程序后获得的较低界限的强度和收敛结果。根据我们的制定和理论结果，我们开发了分支和切割（B＆C）算法，通过起始启动启发式启发式和原始的启发式，它们将进一步增强。 我们使用文献实例评估了B＆C算法的有效性。我们的算法能够解决194个实例中的116个实例，从文献来证明最佳性，对于大多数人来说，运行时间不到一分钟。通过这样做，我们还为116个实例提供了改进的解决方案值。
The discrete $α$-neighbor $p$-center problem (d-$α$-$p$CP) is an emerging variant of the classical $p$-center problem which recently got attention in literature. In this problem, we are given a discrete set of points and we need to locate $p$ facilities on these points in such a way that the maximum distance between each point where no facility is located and its $α$-closest facility is minimized. The only existing algorithms in literature for solving the d-$α$-$p$CP are approximation algorithms and two recently proposed heuristics. In this work, we present two integer programming formulations for the d-$α$-$p$CP, together with lifting of inequalities, valid inequalities, inequalities that do not change the optimal objective function value and variable fixing procedures. We provide theoretical results on the strength of the formulations and convergence results for the lower bounds obtained after applying the lifting procedures or the variable fixing procedures in an iterative fashion. Based on our formulations and theoretical results, we develop branch-and-cut (B&C) algorithms, which are further enhanced with a starting heuristic and a primal heuristic. We evaluate the effectiveness of our B&C algorithms using instances from literature. Our algorithms are able to solve 116 out of 194 instances from literature to proven optimality, with a runtime of under a minute for most of them. By doing so, we also provide improved solution values for 116 instances.
