Computers and Operations Research, vol. 37, pp. 498-508, 2010.
ABSTRACT
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 PageLast modified: 9 October 2009