Description: This article begins with a review of previously proposed integer formulations for the maximum diversity
problem (MDP). This problem consists of selecting a subset of elements from a larger set in such a way
that the sum of the distances between the chosen elements is maximized. We propose a branch and
bound algorithm and develop several upper bounds on the objective function values of partial solutions
to the MDP. Empirical results with a collection of previously reported instances indicate that the pro-
posed algorithm is able to solve all the medium-sized instances (with 50 elements) as well as some
large-sized instances (with 100 elements). We compare our method with the best previous linear integer
formulation solved with the well-known software Cplex. The comparison favors the proposed procedure.
File list (Check if you may need any files):
A branch and bound algorithm for the maximum diversity problem.pdf
Download