.png){kind=icon}
返回
Solving Euclidean Max-Sum problems exactly with cutting planes
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2024.106682.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 maxsum 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.
Keyword:
Euclidean distance matrix
Cutting plane methods
Constrained diversity sum
Exact algorithms
Nonlinear binary optimisation
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容