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

Example 6.8 In Fig. 6.11 , we can obtain Matrix B from A by performing the fol-
lowing init-block reconstruction:
1. Permute symbol '0' and '1' in the first column.
2. Swap rows 1, 2, 3, 4 with rows 5, 6, 7, 8 respectively.
3. Permute symbol '0' and '1' in the last column.

After step 2, the init-block is unchanged. However, the last column of Matrix
A is converted to , contradicting Formula (1) which specifies that

symbol '0' must precede '1'. Step 3 is then performed to adjust the matrix and we
get Matrix B, which satisfies all symmetry breaking constraints. Therefore, A and B
are symmetric w.r.t. the init-block reconstruction.
For an OA

100101101010

1 symmetries caused
by init-block reconstructions except for the identity mapping. To break all these
symmetries, it can be costly, because there are too many swappings and permutations
to perform.
Another technique called Filter [ 5 ] is also useful to break such symmetries. The
basic idea is to add additional constraints to the column adjoining the init-block,
i.e. the

( N , s 1 · s 2 ... s k , t ) , there are s 1 !× s 2 ! ... s t !−

th column. Once a symmetry caused by init-block reconstruction has
been broken in the

( t + 1 )

th column, it is prevented from spreading to the following
columns. It is like setting a filter beyond the init-block, hence the name filter. Filter
can not break all symmetries w.r.t. init-block reconstruction, but it can eliminate
enough isomorphisms, yet the extra cost is negligible.

( t + 1 )

References

1. Cohen, M.B., Dwyer, M.B., Shi, J.: Constructing interaction test suites for highly-configurable
systems in the presence of constraints: a greedy approach. IEEE Trans. Softw. Eng. 34 (5),
633-650 (2008)
2. Flener, P., Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.: Breaking
row and column symmetries in matrix models. In: Proceedings of 8th International Conference
on Principles and Practice of Constraint Programming, pp. 462-477 (2002)
3. Hnich, B., Prestwich, S.D., Selensky, E., Smith, B.M.: Constraint models for the covering test
problem. Constraints 11 (2-3), 199-219 (2006)
4. Law, Y.C., Lee, J.H.: Symmetry breaking constraints for value symmetries in constraint satis-
faction. Constraints 11 (2-3), 221-267 (2006)
5. Ma, F., Zhang, J.: Finding orthogonal arrays using satisfiability checkers and symmetry break-
ing constraints. In: Proceedings of the 10th Pacific Rim International Conference on Artificial
Intelligence (PRICAI), pp. 247-259 (2008)
6. Meagher, K., Stevens, B.: Covering arrays on graphs. J. Comb. Theory Ser. B 95 (1), 134-151
(2005)
7. Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier,
Amsterdam (2006)
8. Schoen, E.D., Eendebak, P.T., Nguyen, M.V.M.: Complete enumeration of pure-level and
mixed-level orthogonal arrays. J. Comb. Des. 18 (2), 123-140 (2010)
9. Walsh, T.: Symmetry breaking using value precedence. In: Proceedings ECAI-06, pp. 168-172
(2006)