Backtracking Search - Automatic Generation of Combinatorial Test Data - page 64

6.3.3.1 Row and Column Symmetries

Flener et al. [ 2 ] identified an important class of symmetries in constraint program-
ming, arising from matrices of decision variables where rows and columns can be
swapped. In general, an m 1 symmetries caused by permu-

tations of rows and columns excluding the identity. It is not practical to generate a
super-exponential number of constraints so as to eliminate all the symmetries. Flener
et al. found that imposing lexicographic order on both the rows and the columns can
break symmetries efficiently, while bringing in only a linear number of constraints.
Lexicographic order is recursively defined as follows:

× n matrix has m !× n !−

Definition 6.2 ( Lexicographic Order ) Two vectors X =[ x 1 , x 2 ,..., x n ] and Y =

[ y 1 , y 2 ,..., y n ] have a lexicographic order X ≤ lex Y if

1. If n = 1, x 1 ≤ y 1 ;

2. If n > 1, x 1 < y 1 ∨ ( x 1 = y 1 ∧[ x 2 ,..., x n ]≤ lex [ y 2 ,..., y n ] ) .

≤ lex Y
does not hold. The rows (columns) of a 2D-matrix are lexicographically ordered if
each row (column) is lexicographically smaller than the next (if any).
Since the init-block of a CA is fixed before search starts, lexicographically order-
ing the rows and columns of the matrix is a bit complex. We have to make sure that
the lexicographic order does not contradict the preset cells.
Assume that the i th row of the matrix is represented as

We say X is lexicographically greater than Y (denoted as X > lex Y )if X

R i =[ ce i , 1 , ce i , 2 ,..., ce i , k ] ,

and the j th column of the matrix is represented as

C j =[ ce 1 , j , ce 2 , j ,..., ce N , j ] .

The constraints for breaking the row and column symmetries in CA are as follows:

1. Suppose R i and R i + 1 ( i > b ) are two adjacent rows outside the init-block, then

R i ≤ lex R i + 1 .
2. Suppose C j and C j + 1 ( j > t ) are two adjacent columns outside the init-block,

then C j ≤ lex C j + 1 .
3. Suppose R i 1 ( i 1 ≤ b ) is a row inside the init-block, and R i 2 ( i 2 > b )isarow

outside the init-block. If ce i 1 , j = ce i 2 , j for all 1 ≤ j ≤ t , then R i 1 ≤ lex R i 2 .

These symmetry breaking constraints are checked on-the-fly during the search.
For example, consider X =[ 1 , 2 , 3 , 4 ] and Y =[ 2 , 3 , ? , ? ] where a “?” represents

an unassigned cell. It is obvious that X ≤ lex Y .

Example 6.3 Consider the three matrices in Fig. 6.3 . Matrix A satisfies all
constraints. In Matrix B, the fourth column is lexicographically greater than the