Optimal results and tight bounds for the maximum diversity problem

The Maximum Diversity Problem (MDP) consists in selecting a subset M of given cardinality out of a set N, in such a way that the sum of the pairwise diversities between the elements of M is maximum. New instances for this problem have been recently proposed in the literature and new algorithms are currently under study to solve them. As a reference for future research, this paper provides a collection of all best known results for the classical and the new instances, obtained by applying the state-of-the-art algorithms. Most of these results improve the published ones. In addition, the paper provides for the first time a collection of tight upper bounds, proving that some of these instances have been optimally solved. These bounds have been computed by a branch-and-bound algorithm based on a semidefinite formulation of the Quadratic Knapsack Problem (QKP), which is a generalization of the MDP.