Better and faster solutions for the maximum diversity problem

The aim of the Maximum Diversity Problem (MDP) is to extract a subset M of given cardinality from a set of elements N, in such a way that the sum of the pairwise distances between the elements of M is maximum. This problem, introduced by Glover [7], has been deeply studied using GRASP methodologies [6, 1, 17, 2, 16]. Usually, effective algorithms owe their success more to the careful exploitation of problem-specific features than to the application of general-purpose methods. A solution for MDP has a very simple structure which can not be exploited for sophisticated neighborhood search. This paper explores the performance of three alternative solution approaches, that is Tabu Search, Variable Neighborhood Search and Scatter Search, comparing them with those of best GRASP algorithms in literature. We also focus our attention on the comparison of these three methods applied in their pure form.