*Result*: Coordinate Partitioning for Difficult Euclidean Max-Sum Diversity Problems.

*Divide and Conquer: Solving the Euclidean Diversity Problem Through Coordinate Partitioning A common technique for solving difficult optimization problems is to break them into easier-to-manage pieces, yet it is rarely obvious how to do so. This is especially true for the Euclidean max-sum diversity problem, which becomes increasingly difficult as the number of coordinates grows despite the problem size remaining the same. In "Coordinate Partitioning for Difficult Euclidean Max-Sum Diversity Problems," Spiers, Bui, and Loxton use an old result by Schoenberg to transform Euclidean distances into their squared counterparts, enabling a functional decomposition of the problem's objective. The authors introduce novel partitioning strategies as well as a globally convergent cutting-plane algorithm, which can effectively solve high-dimension instances. They also present a new class of challenging instances characterized by locations on the surface of a hyperball. The Euclidean max-sum diversity problem becomes substantially more difficult as the number of coordinates increases despite the number of decision variables not changing. In this paper, we overcome this complexity by constructing a new set of locations whose squared Euclidean distances equal that of the original. Using squared distances allows the objective function to be decomposed into the sum of pairwise distances within each coordinate. A partition set of the coordinates is then used to enable a functional decomposition of the objective. Each functional component is expected to be simpler than the original and, therefore, easier to approximate via cutting plane methods. We prove the global convergence of our new approach and introduce several partitioning strategies. Furthermore, we show how a principal component analysis of coordinate influence can be conducted with minimal extra computation, the results of which can be used to guide the partitioning process. Extensive numerical results demonstrate the efficiency of the partitioned cutting-plane method with the algorithm able to solve large, 20-coordinate problems of up to 1,000 locations. Finally, we introduce a new class of challenging diversity problems, characterized by locations situated on the edge of a ball. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)*

*Full text is not displayed to guests* *Login for full access*