3.7.77. Degree of diversity of a set of solutions
A constraint that allows for finding a set of solutions with a certain degree of diversity. As an example, consider the problem of finding 9 diverse solutions for the 10-queens problem. For this purpose we create a 10 by 9 matrix of domain variables taking their values in interval . Each row of corresponds to a solution of the 10-queens problem. We assume that the variables of are assigned row by row, and that within a given row, they are assigned from the first to the last column. Moreover values are tried out in increasing order. We first post for each row of the 3 constraints related to the 10-queens problem (see FigureΒ 5.5.1 for an illustration of the 3 ). With a constraint, we lexicographically order the first two variables of each row of in order to enforce that the first two variables of any pair of solutions are always distinct. We then impose a constraint on the variables of each column of . Let denote the corresponding cost variable associated with the constraint of the -th column of (i.e.,Β the first argument of the constraint). We put a maximum limit (e.g.,Β 3 in our example) on these cost variables. We also impose that the sum of these cost variables should not exceed a given maximum value (e.g.,Β 8 in our example). Finally, in order to balance the diversity over consecutive variables we state that the sum of two consecutive cost variables should not exceed a given threshold (e.g.,Β 2 in our example). As a result we get the following nine solutions depicted below.
,
,
,
,
,
,
,
,
.
The costs associated with the constraints of columns are respectively equal to 1, 1, 1, 0, 1, 0, 1, 1, 1, and 1. The different types of constraints between the previous 9 solutions are illustrated by the next figure.
Figure 3.7.19. Constraint network associated with the problem of finding 9 diverse solutions for the 10-queens problem
Approaches for finding diverse and similar solutions based on theΒ Hamming distance between each pair of solutions are presented by E.Β Hebrard and al. inΒ [HebrardHnichSullivanWalsh05].