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 [0,9]. 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 C i denote the corresponding cost variable associated with the 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπšπš› constraint of the i-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.

  • S 1 =〈0,2,5,7,9,4,8,1,3,6βŒͺ,

  • S 2 =〈0,3,5,8,2,9,7,1,4,6βŒͺ,

  • S 3 =〈1,3,7,2,8,5,9,0,6,4βŒͺ,

  • S 4 =〈2,4,8,3,9,6,1,5,7,0βŒͺ,

  • S 5 =〈3,6,9,1,4,7,0,2,5,8βŒͺ,

  • S 6 =〈5,9,2,6,3,1,8,4,0,7βŒͺ,

  • S 7 =〈6,8,1,5,0,2,4,7,9,3βŒͺ,

  • S 8 =〈8,1,4,9,7,0,3,6,2,5βŒͺ,

  • S 9 =〈9,5,0,4,1,8,6,3,7,2βŒͺ.

The costs associated with the 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπšπš› constraints of columns 1,2,...,10 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
ctrs/fig_degree_of_diversity_network

ctrs/fig_degree_of_diversity_chess1

ctrs/fig_degree_of_diversity_chess2

ctrs/fig_degree_of_diversity_chess3

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].