Solving Euclidean Max-Sum problems exactly with cutting planes
针对欧几里得距离矩阵最大化的非凹二次规划问题，提出两种精确切割平面算法，无需凹重构，在多样性基准问题上优于现有方法，可解至三千变量。
This paper studies binary quadratic programs in which the objective is defined by the maximisation of a Euclidean distance matrix, subject to a general polyhedral constraint set. This class of nonconcave maximisation problems, which we refer to as the Euclidean Max-Sum problem, includes the capacitated, generalised and max-sum diversity problems as special cases. Due to the nonconcave objective, traditional cutting plane algorithms are not guaranteed to converge globally. In this paper, we introduce two exact cutting plane algorithms to address this limitation. The new algorithms remove the need for a concave reformulation, which is known to significantly slow down convergence. We establish exactness of the new algorithms by examining the concavity of the quadratic objective in a given direction, a concept we refer to as directional concavity. Numerical results show that the algorithms outperform other exact methods for benchmark diversity problems (capacitated, generalised and max-sum), and can easily solve problems of up to three thousand variables.