Problem Description

The MaxMin Diversity Problem (MMDP) consists of selecting a subset of m elements from a set of n elements in such a way that the minimum distance between the chosen elements is maximized. This problem is related to Maximum Diversity Problem (MDP) in wich the objective is maximize the sum of the distancies between selected elements. The definition of distance between elements is customized to specific applications. In most applications, it is assumed that each element can be represented by a set of attributes. Let s_ik be the state or value of the k^th attribute of element i, where k = 1, ..., K. Then the distance between elements i and j may be defined as:

In this case, d_ij is simply the Euclidean distance between i and j. The MMDP can be trivially formulated as a linear binary problem with an objective function dependent on the variable values, where for elements i=1,2,…,n, variable x_i takes the value 1 if element i is selected and 0 otherwise; d_ij is the distance between elements i and j, and m is the number of selected elements (m<n)

Erkut (1990) and Ghosh (1996) showed independently that the MMDP is NP-hard.

State of the Art Methods

The most relevant metaheuristics developed to solve this problem are:

• GhoC + BLS: Multi-start method. Ghosh (1996).
• SA: Simulated annealing. Kincaid (1992).
• TS: Tabu search. Kincaid (1992).
• GRASP1: Constructive method GRC2(0.9) coupled with the local search FLS. Resende et al. (2010)
• GPR: Dynamic greedy path relinking. Resende et al. (2010)
• GRASP + EvPR: Evolutionary path relinking. Resende et al. (2010)

Instances (MMDPLIB)

We have compiled a comprehensive set of benchmark instances representative of the collections previously used for computational experiments in the MMDP. We call this benchmark MMDPLIB. A brief description of the origin and the characteristics of the set of instances follows:

• Glover: This data set consists of 75 matrices for which the values were calculated as the Euclidean distances from randomly generated points with coordinates in the 0–100 range. The number of coordinates for each point is also randomly gen- erated between 2 and 21. Glover et al. (1998) developed this test problem generator and constructed instances with n=10, 15, and 30. The value of m ranges from 0.2n to 0.8n.
• Geo: This data set consists of 60 matrices constructed with the same test problem generator employed in the Glover set. We generated 20 instances with n = 100, 250, and 500. For each value of n we consider m=0.1n, 0.3n (generating 10 instances for each combination of n and n). These instances are similar to the geometric instances introduced in Erkut (1990).
• Ran: This data set consists of 60 matrices with random numbers. These instances are based on the generator introduced by Silva et al. (2004). As for the Geo set, we generated 20 instances with n = 100, 250, and 500 (and for each value of n we consider m = 0.1n, 0.3n). The integer random numbers are generated between 50 and 100 in all the instances except when n = 500 and m = 150 in which they are generated between 1 and 200 (to make them harder in terms of comparison among heuristics).

Download the MMDPLIB with all instances.