GRASP and path relinking for the max-min diversity problem

Mauricio G. C. Resende(mgcrresearch.att.com)
Rafael Martí(rafael.martiuv.es)
Micael Gallego(micael.gallegourjc.es)
Abraham Duarte(abraham.duarteurjc.es)

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.

Keywords: Max-Min Diversity Problem, Metaheuristics, Adaptive Memory Programming, GRASP, Path Relinking.

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report TD-7BSN88, AT&T Labs Research, Florham Park, NJ, February 13, 2008.

Download: [PDF]

Entry Submitted: 02/13/2008
Entry Accepted: 02/19/2008
Entry Last Modified: 02/13/2008

Modify/Update this entry