A Breakpoints Based Method for the Maximum Diversity and Dispersion Problems

Hochbaum, D. S., Liu, Z., & Goldschmidt, O. (2023). A Breakpoints Based Method for the Maximum Diversity and Dispersion Problems. In Proceedings of the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23) (pp. 189-200). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977714.17

The maximum diversity, or dispersion, problem (MDP), is to select from a given set a subset of elements of given cardinality (budget), so that the sum of pairwise distances, or utilities, between the selected elements is maximized. We introduce here a method, called the Breakpoints (BP) algorithm, based on a technique proposed in Hochbaum (2009), to generate the concave piecewise linear envelope of the solutions to the relaxation of the problem for all values of the budget. The breakpoints in this envelope are provably optimal for the respective budgets and are attained using a parametric cut procedure that is very efficient. The performance of the parametric cut is further enhanced by a newly introduced compact formulation of the problem. The problem is then solved, for any given value of the budget, by applying a greedy-like method to add or subtract nodes from adjacent breakpoints. This greedy solution may be improved using Tabu Search, the BPTS algorithm. This method works well if for the given budget there are breakpoints that are “close”. However, for many data sets and budgets this is not the case, and the breakpoints are sparse. We introduce a perturbation technique applied to the utility values in cases where there is paucity of breakpoints, and show that this results in denser collections of breakpoints. Furthermore, each optimal perturbed solution is quite close to an optimal non-perturbed solution. We compare the performance of our breakpoints algorithm to leading methods for these problems: The metaheuristic OBMA-that was recently shown to outperform GRASP, Neighborhood search and Tabu Search-and Gurobi, an integer programming software. It is demonstrated that our method dominates, dramatically, the performance of these methods in terms of computation speed and in comparable or better solution quality. This is the first time that the properties of the concave envelope and the breakpoints are used in a practically tested algorithm. This implies the potential of this method for more general submodular maximization problems.