论文标题
解决p分散问题问题的精确切割平面方法
An exact cutting plane method for solving p-dispersion-sum problems
论文作者
论文摘要
本文旨在回答文献中最近提出的一个空旷的问题，即找到一种快速精确的方法来解决p分散性问题（PDSP），这是一种非漫画二进制二进制二进制最大化问题。我们表明，由于定义二次项（PDSP）中定义二次项的欧几里得距离矩阵始终是负面的，因此即使在没有凹度的情况下，切割平面方法也适用于（PDSP）。因此，主要用于凹面最大化问题的切割平面方法收敛到（PDSP）的最佳解决方案。数值结果表明，该方法的表现优于求解的其他精确方法（PDSP），并且可以求解最大实例的最佳实例，该实例的大量变量多达两千个变量。
This paper aims to answer an open question recently posed in the literature, that is to find a fast exact method for solving the p-dispersion-sum problem (PDSP), a nonconcave quadratic binary maximization problem. We show that, since the Euclidean distance matrix defining the quadratic term in (PDSP) is always conditionally negative definite, the cutting plane method is exact for (PDSP) even in the absence of concavity. As such, the cutting plane method, which is primarily designed for concave maximisation problems, converges to the optimal solution of the (PDSP). The numerical results show that the method outperforms other exact methods for solving (PDSP), and can solve to optimality large instances of up to two thousand variables.
