

![0_image_0.png](0_image_0.png)

Table 1. Static symmetry breaking constraints vs Model restarts and SBDS on Graph Coloring problems. "opt" is the quality of the solution found (* indicates optimality was not proved), "t" is the runtime in seconds, "b" is the number of backtracks. The best method for a problem instance is in **bold font**.

Instance Static constraints Model Restarts SBDS

Lex Random Lex Random Lex Random

t b t b t b t b t b t b

3-3-4-5 0.01 176 **0.01** 246 0.02 271 0.2 3504 0.06 2060 **0.01** 318

3-4-6-5 0.02 599 0.04 726 0.04 703 0.59 7340 0.03 855 **0.01 465** 4-3-3-3 **0 34** 0.01 141 0.12 1570 0.08 1013 0.01 51 0 57

4-3-4-5 0.02 326 0.14 2392 0.28 3821 0.14 1629 0.16 4177 **0.01 42**

4-3-5-4 0 91 0.06 1204 0.12 1497 0.23 4055 0 52 **0 51**

4-4-4-5 0.07 1350 0.03 314 1.77 17 K 6.88 98 K **0 41** 0.04 930 4-4-5-4 0.02 504 0.27 3956 1.01 8941 1.03 10 K **0.01 208** 0.04 790 4-6-4-5 45.43 763 K - - 0.27 2612 0.67 5104 6.59 111 K **0.04 629**

5-3-3-4 **0.01 190** 0.06 937 6.64 75 K 3.6 63 K 0.14 3113 0.02 382

5-3-4-5 **0.03 527** 1.51 21 K 4.34 45 K 1.32 13 K 1.16 26 K 0.12 2109 6-3-4-5 0.25 4538 2.84 40 K 3.9 44 K 9.06 106 K 5.92 114 K 0.06 1380

Table 2. Static symmetry breaking constraints vs Model restarts and SBDS on EFPA problems. "t" is the runtime in seconds, "b" is the number of backtracks.

The best method for a problem instance is in **bold font**.

veloping methods for dynamically posting a symmetry of the symmetry breaking constraints which does not conflict with the branching heuristic. In the longer term, we would like to exploit symmetries of the nogoods learnt during search. Nogoods are themselves just constraints. We can therefore consider symmetries acting on them.

## References

[1] D. Cohen, P. Jeavons, C. Jefferson, K.E. Petrie, and B.M. Smith, 'Symmetry definitions for constraint satisfaction problems', *Constraints*,
11(2–3), 115–137, (2006).

[2] J. Crawford, M. Ginsberg, G. Luks, and A. Roy, 'Symmetry breaking predicates for search problems', in *5th Int. Conf. on Knowledge Representation and Reasoning, (KR '96)*, pp. 148–159, (1996).

[3] T. Fahle, S. Schamberger, and M. Sellmann, 'Symmetry breaking', in 7th Int. Conf. on Principles and Practice of Constraint Programming
(CP2001), pp. 93–107. (2001).

[4] P. Flener, A. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, J. Pearson, and T. Walsh, 'Breaking row and column symmetry in matrix models', in 8th Int. Conf. on Principles and Practices of Constraint Programming (CP-2002). (2002).

[5] A. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, and T. Walsh, 'Global constraints for lexicographic orderings', in 8th Int. Conf. on Principles and Practices of Constraint Programming (CP-2002). (2002).

[6] A. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, and T. Walsh, 'Propagation algorithms for lexicographic ordering constraints', *Artificial Intelligence*, 170(10), 803–908, (2006).

[7] I.P. Gent and B.M. Smith, 'Symmetry breaking in constraint programming', in *ECAI-2000*, pp. 599–603. (2000).

[8] I.P. Gent and T. Walsh, 'CSPLib: a benchmark library for constraints',
Technical report, Technical report APES-09-1999, (1999). A shorter version appears in Proc. of CP-99.

[9] C. Gomes, B. Selman, and H. Kautz, 'Boosting combinatorial search through randomization', in *15th National Conf. on Artificial Intelligence*, pp. 431–437. (1998).

[10] D. Heller, A. Panda, M. Sellmann, and J. Yip, 'Model restarts for structural symmetry breaking', in *14th Int. Conf. on the Principles and Practice of Constraint Programming*, pp. 539–544, (2008).

![0_image_1.png](0_image_1.png)

![0_image_2.png](0_image_2.png)

![0_image_3.png](0_image_3.png)

![0_image_4.png](0_image_4.png)

[11] S. Huczynska, P. McKay, I. Miguel, and P. Nightingale, 'Modelling equidistant frequency permutation arrays: An application of constraints to mathematics', in 15th Int. Conf. on the Principles and Practice of Constraint Programming, pp. 50–64. (2009).

[12] C. Jefferson, T. Kelsey, S. Linton, and K. Petrie, 'Gaplex: Generalised static symmetry breaking', in *6th Int. Workshop on Symmetry in Constraint Satisfaction Problems, held alongside CP-06*, (2006).

[13] Y.-C. Law, J. Lee, T. Walsh, and J. Yip, 'Breaking symmetry of interchangeable variables and values', in 13th Int. Conf. on Principles and Practices of Constraint Programming (CP-2007). (2007).

[14] Y.C. Law and J.M.H. Lee, 'Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction', *Constraints*, 11(2–3), 221–267, (2006).

[15] J.-F. Puget, 'On the satisfiability of symmetrical constrained satisfaction problems', in *Proc. of ISMIS'93*, pp. 350–361. (1993).

[16] J-F. Puget, 'Symmetry breaking using stabilizers', in 9th Int. Conf. on Principles and Practice of Constraint Programming (CP2003), (2003).

[17] C. Roney-Dougal, I. Gent, T. Kelsey, and S. Linton, 'Tractable symmetry breaking using restricted search trees', in *ECAI-2004*. (2004).

[18] I. Shlyakhter, 'Generating effective symmetry-breaking predicates for search problems', in *Proc. of LICS workshop on Theory and Applications of Satisfiability Testing (SAT 2001)*, (2001).

[19] T. Walsh, 'Symmetry breaking using value precedence', in *ECAI-2006*,
pp. 168–172. (2006).

[20] T. Walsh, 'Breaking value symmetry', in *13th Int. Conf. on Principles* and Practices of Constraint Programming (CP-2007). (2007).

[21] T. Walsh, 'Breaking value symmetry', in Proc. of the 23rd National Conf. on AI, pp. 1585–1588. AAAI, (2008).