mdp-description.md

Scatter Search Applied to the MDP

🏠 Home · ← Prev: CPH — Implementation

Introduction

The Maximum Diversity Problem (MDP) consists of selecting a set of elements from a larger collection so that the selected elements have the most varied characteristics among themselves (Kuo et al., 1993). An example application of this problem arises in biodiversity preservation. In that setting, a limited number of resources is available to save only a given number of species. Here it is more appropriate to save the species that display the most varied set of characteristics.

From a computational point of view, the MDP is an intractable problem; that is, no algorithm is known that guarantees obtaining a solution (and verifying that it is optimal) within a reasonable amount of running time. For this reason, it becomes necessary to build an approximate algorithm to solve it. From a mathematical point of view, and letting $d_{ij}$ be the distance between elements $i$ and $j$, the MDP can be formulated as the following binary quadratic problem:

$$ \text{MDP} = \begin{cases} \max: & \displaystyle \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} d_{ij},x_i x_j \[4pt] \text{s.t.} & \[2pt] & \displaystyle \sum_{i=1}^{n} x_i = m \[4pt] & x_i \in {0,1}, \quad 1 \leq i \leq n \end{cases} $$

Kuo et al. (1993) use this formulation to show that the clique problem (which is $\mathcal{NP}$-complete) is reducible to the MDP. As indicated in that same work, the maximum diversity problem appears in a wide variety of real-world problems. Today, many universities in the United States, when determining their admission policies, go beyond selecting by academic grade and also consider other factors in the search for a diverse set of students. In market planning, it is frequently desirable to maximize the number and diversity of forces in a brand profile. Other contexts in which the maximum diversity problem can be applied include plant breeding, social problems, ecological preservation, product design, workforce management, curriculum design, and the management of genetic resources. Diversity maximization is also an important aspect in the following areas: chemical experimentation, experimental design, medical research, geological exploration, investment portfolio selection, and structural engineering.

Nº	Sex	Race	Region	Education	Class	Political
1	Female	White	West	Higher voc.	Middle	Right
2	Male	White	East	University	Middle	Nonpartisan
3	Male	Black	West	High school	Lower-middle	Left
4	Female	Black	Center	Basic	Lower-middle	Right
5	Female	White	Center	University	High	Nonpartisan
6	Male	Black	East	University	Middle	Nonpartisan
7	Male	White	West	Higher voc.	High	Left
8	Male	White	Center	High school	Low	Right
9	Male	White	East	Higher voc.	Middle	Left
10	Female	Black	East	University	High	Right

Table 1. Characterized inhabitants.

A Detailed Example

To illustrate the maximum diversity problem, a complete example based on Kuo et al. (1993) is presented. Consider the inhabitants of a city characterized by their sex, race, education, etc., as shown in Table 1. For a pollster who can only conduct a given number of surveys, it is useful to choose those inhabitants with the most varied characteristics among themselves. The problem can be modeled as an instance of the MDP. The first step is to define a distance between each pair of inhabitants. To do so, we choose a numerical encoding for each characteristic as shown in Table 2.

Characteristic	Value 1	Value 2	Value 3	Value 4
Sex	Male	Female
Race	White	Black
Region	East	Center	West
Education	Basic	High school	Higher voc.	University
Class	Low	Lower-middle	Middle	High
Political	Left	Nonpartisan	Right

Table 2. Encoding of characteristics.

Applying that encoding, the inhabitants are defined as vectors in a seven-dimensional space (one dimension $K$ per characteristic) as shown in Table 3. If we define $s_{ik}$ as the value of dimension $k$ of element $i$, and we consider that how different two inhabitants are from each other corresponds to the Euclidean distance of the vectors that represent them, we define the distance $d_{ij}$ as:

$$ d_{ij} = \sqrt{\sum_{k=1}^{K} (s_{ik} - s_{jk})^2} $$

Nº	Sex	Race	Region	Education	Class	Political
1	2	1	3	3	3	3
2	1	1	1	4	3	2
3	1	2	3	2	2	1
4	2	2	2	1	2	3
5	2	1	2	4	4	2
6	1	2	1	4	3	2
7	1	1	3	3	4	1
8	1	1	2	2	1	3
9	1	1	1	3	3	1
10	2	2	1	4	4	3

Table 3. Representation of the inhabitants as vectors in a 7-dimensional space.

We can therefore compute a distance matrix containing the distance between each pair of inhabitants. This matrix appears in Table 4. For this particular example we are going to select the 3 most varied inhabitants; that is, we have to model the problem as an MDP with $n = 10$ and $m = 3$ and with the distance matrix of Table 4. The MDP consists of choosing 3 inhabitants so that the sum of the distances among them is maximal. In this example, the 3 most diverse inhabitants are 6, 7, and 9, with the maximum value for the sum of their distances, which is 11.19.

	2	3	4	5	6	7	8	9	10
1	2.65	2.83	2.65	2	2.83	2.45	2.65	3	2.65
2		3.32	3.74	1.73	1	2.65	3.16	1.41	2
3			2.65	3.46	3.16	2.45	2.65	2.65	4.12
4				3.87	3.61	3.87	2	3.46	3.74
5					2	2	3.87	2.24	1.73
6						2.83	3.32	1.73	1.73
7							3.87	2.24	3.32
8								3.16	4
9									2.83

Table 4. Distance matrix of the inhabitants.

Applying Scatter Search

To apply a metaheuristic framework such as scatter search to a specific problem, it is necessary to design some parts of the framework specifically for it. In particular, for scatter search, it is necessary to define a distance between solutions, so that it can be used when solutions are selected by diversity. In addition, the methods for generating diverse solutions, generating subsets, combining solutions, and the improvement method must be designed.

To determine the most suitable methods, three variants of scatter search for the MDP have been implemented. The differences between these variants are based on the methods used to build diverse solutions, combine solutions, and improve them. Table 5 lists the methods used in each of the configurations. The procedure called "No information" does not use any problem-specific information. The procedure called "With information" implements several MDP-specific strategies. The "With memory" procedure uses, in addition to problem information, memory structures that are typical of tabu search implementations (Glover & Laguna, 1997).

Through several preliminary experiments, it was decided to use a $RefSet$ of size 12, and the percentage of solutions in it that are incorporated by quality is 30%.

Configuration	Solution Generation	Combination	Improvement
No information	Random selection of $m$ elements from all $n$ problem elements	Random selection of $m$ elements from the union of the elements of the solutions being combined	Best-improvement Local Search (LS)
With information	GRASP_D-2, based on randomizing the D-2 destructive heuristic	Applying D-2 to the union of the elements of the solutions being combined	First-improvement Improved Local Search (I_LS)
With memory	Tabu_D-2, based on adding memory structures to D-2	Applying Tabu_D-2 to the union of the elements of the solutions being combined	Local Search Tabu Search (LS_TS) with short-term memory

Table 5. Scatter search variants.

The following subsections define the distance between solutions and each of the methods used in each variant. In addition, the last subsection mentions an improvement made to the general scatter search scheme.

Distance Between Solutions

The distance is used to measure how diverse a solution is with respect to a set of solutions. Specifically, for the MDP, $x_i^y$ is defined as the value of the $i$-th variable of the reference solution $r \in RefSet$. We also define $x_i^t$ as the value of the $i$-th variable of the candidate solution $t$. The distance between a candidate solution $t$ and the solutions in the $RefSet$, in the proposed scatter search implementation, is defined as:

$$ \text{distance}(t, RefSet) = c_{max} - \sum_{y=1}^{b} \sum_{i,:,x_i^t = 1} x_i^y $$

The formula simply counts the number of times each element selected in the candidate solution $t$ appears in any of the $RefSet$ solutions and subtracts this value from the largest count $c_{max}$. The maximum distance occurs when no element that is selected in the candidate solution $t$ appears in any of the reference solutions. When solutions are chosen to rebuild the reference set, we select the candidate solution that has the maximum distance to the $RefSet$ solutions. Since solutions are incorporated one at a time, the distance computation has to be updated before the next solution is selected.

Methods for Generating Diverse Solutions

This section describes the methods used in the different configurations for generating diverse solutions.

Random Selection

This method consists of selecting $m$ elements out of the total of $n$ problem elements. Random selection does not use any MDP information; for example, it does not use the objective function to guide the constructive process. The only information used is the number $m$ of elements needed to build a feasible solution.

GRASP_D-2

The GRASP_D-2 procedure, developed by Duarte & Martí (2006), is based on randomizing the destructive heuristic developed by Glover, Kuo & Dhir (1998). D-2 starts with an infeasible solution for which $x_i = 1$ for all $i$; that is, all $n$ elements are initially selected. To reduce the set of selected elements down to $m$, the procedure performs $n - m$ steps. At each step, the procedure deselects element $i^$ (that is, $x_i = 0$), where $i^$ is such that:

$$ \begin{aligned} & D(i^*) = \min_{i,:,x_i = 1}\big(D(i)\big) \\ & \text{with} \quad D(i) = \sum_{j} d_{ij},x_i x_j \end{aligned} $$

The randomization of D-2 used in GRASP_D-2 consists of selecting $i^$ from a Reduced Candidate List (RCL) formed by all those elements $i$ such that $D(i) \leq (1 - \alpha) D(i^)$. The value of $\alpha$ is initially set to 0.5 and is decremented by 0.1 after a predefined running time has been consumed without obtaining a solution of better quality than the previous ones. In our case, this value has been set to 20% of the total experimentation CPU time.

Tabu_D-2

The Tabu_D-2 method was presented in Duarte & Martí (2006). It is based on adding memory structures to the D-2 method. At each step of the procedure, the element $i^*$ that is deselected is the one that satisfies:

$$ D(i^*) = \min_{i,:,x_i = 1}\big(D(i) - \text{freqW} - \text{qualW}\big) $$

where

$$ \begin{aligned} \text{freqW} &= \beta,(\text{range}) \left( \frac{f(i)}{f_{max}} \right) \[4pt] \text{qualW} &= \delta,(\text{range}) \left( \frac{q(i)}{q_{max}} \right) \[4pt] \text{range} &= \max_{i,:,x_i = 1}(D(i)) - \min_{i,:,x_i = 1}(D(i)) \end{aligned} $$

In this modified distance computation, $f(i)$ indicates the frequency with which element $i$ has appeared in previous solutions, and $q(i)$ is the average quality (measured by the objective function) of the previous solutions that included element $i$. Both $f_{max}$ and $q_{max}$ are the maximum values of $f$ and $q$ over all elements. The weighting factors $\beta$ and $\delta$ are set to 0.1 and 0.0001, respectively, in our experiments.

Subset Generation Method

The simplest method for subset generation has been considered. This method consists of generating one subset for each distinct pair of the solutions to be combined.

Combination Methods

This section describes the methods used for combining solutions in each of the scatter search variants presented. To illustrate the different methods, we use the detailed example presented in the introduction to the MDP. Suppose that, during the execution of the algorithm, two reference solutions $r_1$ and $r_2$ have to be combined. To simplify the notation, we present each solution as the set of selected nodes: $r_1 = {1, 4, 6}$ and $r_2 = {1, 5, 10}$. The objective-function values associated with these solutions are 9.09 (2.65 + 2.83 + 3.61) and 6.38 (2 + 2.65 + 1.73), respectively.

Random Selection

This method consists of selecting $m$ elements from the union of the elements in both reference solutions. In our example, the union of the elements is $U = {1, 4, 5, 6, 10}$. Random selection consists of selecting 3 elements from $U$. For example, the new candidate solution could be $t = {1, 4, 10}$, whose objective-function value is 9.04 (2.65 + 2.65 + 3.74).

D-2 Selection

This method consists of applying the D-2 destructive heuristic to the union of the elements of the solutions being combined. The method starts by selecting all the elements in the union and deselects one element at a time until only $m$ elements remain selected. The element $i$ that is deselected at each step is the one that has the minimum $D(i)$ value. In our example, the union consists of 5 elements, so the method performs only two steps. In the first step, the $D$ values are:

$$ \begin{aligned} D(1) &= d(1,4) + d(1,5) + d(1,6) + d(1,10) = 2.65 + 2 + 2.83 + 2.65 = 10.13 \\ D(4) &= d(4,1) + d(4,5) + d(4,6) + d(4,10) = 2.65 + 3.87 + 3.61 + 3.74 = 13.87 \\ D(5) &= d(5,1) + d(5,4) + d(5,6) + d(5,10) = 2 + 3.87 + 2 + 1.73 = 13.22 \\ D(6) &= d(6,1) + d(6,4) + d(6,5) + d(6,10) = 2.83 + 3.61 + 2 + 1.73 = 10.17 \\ D(10) &= d(10,1) + d(10,4) + d(10,5) + d(10,6) = 2.65 + 3.74 + 1.73 + 1.73 = 9.85 \end{aligned} $$

The minimum $D$ value corresponds to element 10, so this element is deselected. The updated union is $U = {1, 4, 5, 6}$. For the next step, the corresponding $D$ values are 7.48, 10.13, 7.87, and 8.44. Therefore, element 1 is deselected, and the candidate solution that results from applying this combination method is $t = {4, 5, 6}$ with an objective-function value equal to 9.48.

Tabu_D-2 Selection

This consists of applying the Tabu_D-2 procedure to the union of the elements of the reference solutions that have to be combined. This method uses information about the solutions generated in the past, as well as information associated with those combined solutions. To illustrate how the procedure works, a combination based on the example from A Detailed Example is presented. For this, we assume that after a number of iterations the information in Table 6 is available.

Element	Frequency	Quality
1	13	7.73
2	19	7.25
3	17	8.69
4	8	9.37
5	45	6.64
6	17	7.71
7	16	8.42
8	16	9.09
9	19	7.44
10	13	8.50

Table 6. Information about previous solutions.

We use Table 6 to compute the modified $D$ values as described above for the Tabu_D-2 method.

$$ \begin{aligned} D(1) &= 10.13 - (0.02)(13) + (0.000043)(7.73) = 9.87 \\ D(4) &= 13.87 - (0.02)(8) + (0.000043)(9.37) = 13.71 \\ D(5) &= 13.22 - (0.02)(45) + (0.000043)(6.64) = 12.32 \\ D(6) &= 10.17 - (0.02)(17) + (0.000043)(7.71) = 9.83 \\ D(10) &= 9.85 - (0.02)(13) + (0.000043)(8.50) = 9.59 \end{aligned} $$

The minimum $D$ value corresponds to element 10, so this element is deselected. The updated union is $U = {1, 4, 5, 6}$. For the next step, the corresponding values are 7.30, 10, 7.24, and 8.20. Therefore, element 5 is deselected, and the candidate solution that results from applying this combination method is $t = {1, 4, 6}$ with an objective-function value equal to 9.09.

Improvement Methods

This section describes the methods used for improving solutions in each of the scatter search variants presented.

Local Search (LS)

The Local Search (LS) method (Ghosh, 1996) scans the set of selected elements looking for the best swap to replace a selected element with an unselected one. The method performs moves as long as the objective-function value increases. It ends its execution when no element swap that improves the solution can be found. This improvement method is classified among the methods that apply the move that improves the most; that is, the best move (best improvement).

Improved Local Search (I_LS)

The Improved Local Search (I_LS) method (Duarte & Martí, 2006) selects the element $i^$ ($x_{i^} = 1$) that provides the smallest contribution to the objective-function value of the current solution. It then looks for an element $j$ ($x_j = 0$) to be swapped with $i^$. The first element $j$ that results in an improving move is selected, and the swap is performed without examining the remaining unselected elements. If no improving move that swaps $j$ for $i^$ is found, the element with the next smallest contribution is examined. This process continues until no improving move is found.

Local Search Tabu Search (LS_TS)

The improvement method used in the Hybrid Tabu Search configuration is based on the Local Search Tabu Search (LS_TS) method (Duarte & Martí, 2006). It implements a short-term tabu search method based on swaps. An iteration of this method begins with the selection of the element $i$ ($x_i = 1$) with the smallest $D(i)$ value. The list of unselected elements is reviewed and the first swap move of elements $i$ and $j$ ($x_j = 0$) that improves the objective function is selected. If no improving move is found, then the move that worsens the least is chosen. The chosen swap is performed, and both elements that participate in the swap are classified as tabu-active for a number of iterations (known as the tabu tenure). Tabu-active elements are not allowed to participate in swaps. The LS_TS method ends after a consecutive number of iterations in which the solution has not been improved.

The original LS_TS method was modified when it was added to our scatter search framework. The modification consists of using an asymmetric tabu tenure in which the elements added to the solution have a smaller tabu tenure than the one assigned to the elements that have been removed from the solution. Also, the tabu tenure and the maximum number of iterations have been made dependent on the number of elements in the solution. According to the experimentation presented in Duarte & Martí (2006), the tabu tenure of the selected elements is set to $0.28m$ iterations, while the tabu tenure for the unselected elements is $0.028(n - m)$. The maximum number of iterations without improvement is set to $0.1(n - m)$.

Filter in the Improvement Method

In some initial tests during the design of the algorithm, it was detected that the diversification and combination methods obtain the same solution more than once. To avoid applying the improvement method to the same solution more than once, a hash map data structure was developed. This data structure stores all solutions and their corresponding improvement. It is indexed using the hash function of the algorithm below. This hash function was selected because it is the default implementation for the encoding used in the Java programming language.

$$ \begin{aligned} &{hash} = \text{computeHash}(x_i : \text{SolutionType}) \\ &\quad hash := 1 \\ &\quad \textbf{for } i := 1 \textbf{ to } n \textbf{ do} \\ &\qquad hash := 31 \cdot hash + 1231 \cdot x_i + 1237 \cdot (1 - x_i) \\ &\quad \textbf{end for} \end{aligned} $$

Algorithm 1. Hash function.

This method is able to filter 0.5% of the solutions in the Hybrid GRASP procedure and 82% of the solutions in the Hybrid Tabu Search procedure. Before applying the improvement procedure, the hash function is used to check whether that solution already exists in the data structure. In that case, the previously improved solution — which is also stored in the data structure — is used.

---

References

• Kuo, C.-C., Glover, F., & Dhir, K. S. (1993). Analyzing and modeling the maximum diversity problem by zero-one programming.
• Glover, F., & Laguna, M. (1997). Tabu Search.
• Glover, F., Kuo, C.-C., & Dhir, K. S. (1998). Heuristic algorithms for the maximum diversity problem.
• Ghosh, J. B. (1996). Computational aspects of the maximum diversity problem.
• Duarte, A., & Martí, R. (2006). Tabu search and GRASP for the maximum diversity problem.

---

Next: MDP — Implementation →