Tabu Search vs. GRASP for the Maximum Diversity Problem

The Maximum Diversity Problem (MDP) consists in determining a subset M of given cardinality from a set of elements N, in such a way that the sum of the pairwise differences between the elements of M is maximum. This problem, introduced by Glover, Hersh and McMillian has been deeply studied using the GRASP methodology. GRASPs are often characterized by a strong design effort dedicated to the randomized generation of high quality starting solutions, while the subsequent improvement phase is usually performed by a standard local search technique. The purpose of this paper is to explore a somewhat opposite approach, that is to refine the local search phase, by adopting a Tabu Search methodology, while keeping a very simple initialization procedure. Extensive computational results show that Tabu Search achieves both better results and much shorter computational times with respect to those reported for GRASP.