New heuristics for the maximum diversity problem

The maximum diversity problem (MDP) consists of identifying, in a population, a subset of elements, characterized by a set of attributes, that present the most diverse characteristics among the elements of the subset. The identification of such solution is an NP-hard problem. Some heuristics are available to obtain approximate solutions for this problem. In this paper, we propose different GRASP heuristics for the MDP, using distinct construction procedures and including a path-relinking technique. Performance comparison among related work and the proposed heuristics is provided. Experimental results show that the new GRASP heuristics are quite robust and are able to find high-quality solutions in reasonable computational times. G.C. Silva’s work sponsored by CAPES MSc scholarship. L.S. Ochi’s work sponsored by CNPq research grants 304103/2003-9 and 550059/2005-9. S.L. Martins’s work sponsored by CNPq research grant 475124/03-0. A. Plastino’s work sponsored by CNPq research grants 300879/00-8 and 475124/03-0.