Optimal results and tight bounds for the maximum diversity problem
Roberto Aringhieri, Maurizio Bruglieri, Roberto Cordone · Institutional Research Information System University of Turin (University of Turin) · 2009
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.