Gaar Elisabeth, Sinnl Markus
Institute of Production and Logistics Management Johannes Kepler University Linz Linz Austria.
JKU Business School Johannes Kepler University Linz Linz Austria.
Networks (N Y). 2023 Dec;82(4):371-399. doi: 10.1002/net.22162. Epub 2023 Jun 13.
The discrete -neighbor -center problem (d--CP) is an emerging variant of the classical -center problem which recently got attention in literature. In this problem, we are given a discrete set of points and we need to locate 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--CP are approximation algorithms and two recently proposed heuristics. In this work, we present two integer programming formulations for the d--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.
离散邻域中心问题（d--CP）是经典中心问题的一种新兴变体，最近在文献中受到了关注。在这个问题中，我们给定一组离散的点，需要在这些点上定位设施，使得每个没有设施的点与其最近设施之间的最大距离最小化。文献中现有的求解d--CP的算法只有近似算法和最近提出的两种启发式算法。在这项工作中，我们给出了d--CP的两种整数规划公式，以及不等式的提升、有效不等式、不改变最优目标函数值的不等式和变量固定程序。我们给出了关于这些公式强度的理论结果，以及以迭代方式应用提升程序或变量固定程序后得到的下界的收敛结果。基于我们的公式和理论结果，我们开发了分支定界（B&C）算法，并用一种起始启发式算法和一种原始启发式算法对其进行了进一步增强。我们使用文献中的实例评估了我们的B&C算法的有效性。我们的算法能够将文献中194个实例中的116个求解到已证明的最优解，其中大多数实例的运行时间不到一分钟。通过这样做，我们还为116个实例提供了改进的解值。
