GRASP and path relinking for the max-min diversity problem

M.G.C. Resende, R. Martí, M. Gallego, and A. Duarte

Computers and Operations Research, vol. 37, pp. 498-508, 2010.


The Max-Min Diversity Problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among  the selected elements is maximized.  The problem is NP-hard and can be formulated as an integer linear program.  Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in the social and biological sciences. We propose a heuristic method - based on the GRASP and path relinking methodologies - for finding approximate solutions to this optimization problem.  We explore different ways to hybridize GRASP and path relinking, including the recently proposed variant known as GRASP with evolutionary path relinking.  Empirical results indicate that the proposed hybrid implementations compare favorably to previous metaheuristics, such as tabu search and simulated annealing.

PDF file of full paper
Mauricio G.C. Resende's Home Page
Last modified: 9 October 2009

Copyright Notice