3.7.79. Degree of diversity of a set of solutions

modelling: degree of diversity of a set of solutions A constraint that allows 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 to 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 in increasing order. We first post for each row of β„³ the 3 πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints related to the 10-queens problem (see FigureΒ 5.12.2 for an illustration of the 3 πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints). 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 one of the possible results 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 FigureΒ 3.7.23. The nine diverse solutions S 1 ,S 2 ,β‹―,S 9 are shown by FigureΒ 3.7.24. FigureΒ 3.7.25 depicts the distribution of all the queens of the nine solutions on a unique chessboard.

Figure 3.7.23. Constraint network associated with the problem of finding 9 diverse solutions for the 10-queens problem where variables are fixed to the solutions corresponding to 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 9 =〈9,5,0,4,1,8,6,3,7,2βŒͺ, and where each type of constraint (hyperedge) is drawn with its own colour
Figure 3.7.24. Nine diverse solutions to the 10-queens problem
Figure 3.7.25. Distribution of the queens on the chessboard of the nine diverse solutions depicted by FigureΒ 3.7.24 to the 10-queens problem: a red queen means two queens from two different solutions that are placed on a same cell, non-red queens of a same colour are queens that belong to a same solution; out of the 10Β·10 cells of the original chessboard, 9Β·10-2Β·8=74 cells are occupied by a single queen, 8 by two queens, and 18 by no queen at all.

Approaches for finding diverse and similar solutions based on theΒ Hamming distances between each pair of solutions are presented by E.Β Hebrard et al. Β [HebrardHnichSullivanWalsh05].