Coordinate Partitioning for Difficult Euclidean Max-Sum Diversity Problems

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.