Abstract
A common type of symmetry is when both variables and values partition into interchangeable sets. Polynomial methods have been introduced to eliminate all symmetric solutions introduced by such interchangeability. Unfortunately, whilst eliminating all symmetric solutions is tractable in this case, pruning all symmetric values is NP-hard. We introduce a new global constraint called SigLex and its GAC propagator for pruning some (but not necessarily all) symmetric values. We also investigate how different postings of the SigLex constraints affect the pruning performance during constraint solving. Finally, we test these static symmetry breaking constraints experimentally for the first time.
We thank the anonymous referees for their constructive comments. The work described in this paper was substantially supported by grants (Project no. CUHK4131/05 and CUHK4219/04E) from the Research Grants Council of the Hong Kong SAR. NICTA is funded by DCITA and ARC through Backing Australia’s Ability and the ICT Centre of Excellence program.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Puget, J.F.: On the satisfiability of symmetrical constrained satisfaction problems. In: Proc. of ISMIS 1993, pp. 350–361 (1993)
Crawford, J., Luks, G., Ginsberg, M., Roy, A.: Symmetry breaking predicates for search problems. In: Proc. of KR 1996, pp. 148–159 (1996)
Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.: Breaking row and column symmetry in matrix models. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 462–476. Springer, Heidelberg (2002)
Law, Y.C., Lee, J.: Global constraints for integer and set value precedence. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 362–376. Springer, Heidelberg (2004)
Fahle, T., Schamberger, S., Sellmann, M.: Symmetry breaking. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 93–107. Springer, Heidelberg (2001)
Gent, I., Smith, B.: Symmetry breaking in constraint programming. In: Proc. of ECAI 2000, pp. 599–603 (2000)
Roney-Dougal, C., Gent, I., Kelsey, T., Linton, S.: Tractable symmetry breaking using restricted search trees. In: Proc. of ECAI 2004, pp. 211–215 (2004)
Walsh, T.: Breaking value symmetry. In: Proc. of CP 2007 (2007)
Flener, P., Pearson, J., Sellmann, M., Van Hentenryck, P.: Static and dynamic structural symmetry breaking. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 695–699. Springer, Heidelberg (2006)
Sellmann, M., Van Hentenryck, P.: Structural symmetry breaking. In: Proc. of IJCAI 2005, pp. 298–303 (2005)
Pesant, G.: A regular language membership constraint for finite sequences of variables. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 295–482. Springer, Heidelberg (2004)
Quimper, C., van Beek, P., Lopez-Ortiz, A., Golynski, A.: Improved algorithms for the global cardinality constraint. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 542–556. Springer, Heidelberg (2004)
Quimper, C., Walsh, T.: Global grammar constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 751–755. Springer, Heidelberg (2006)
Puget, J.F.: Automatic detection of variable and value symmetries. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 475–489. Springer, Heidelberg (2005)
Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Propagation algorithms for lexicographic ordering constraints. Artificial Intelligence 170, 803–908 (2006)
Walsh, T.: Symmetry breaking using value precedence. In: Proc. of ECAI 2006, pp. 168–172 (2006)
Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30, 479–513 (1983)
Law, Y.C., Lee, J.: Symmetry breaking constraints for value symmetries in constraint satisfaction. Constraints 11, 221–267 (2006)
Puget, J.F.: Breaking symmetries in all different problems. In: Proc. of IJCAI 2005, pp. 272–277 (2005)
Puget, J.F.: Breaking all value symmetries in surjection problems. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 490–504. Springer, Heidelberg (2005)
Firsch, A., Jefferson, C., Miguel, I.: Symmetry breaking as a prelude to implied constraints: A constraint modelling pattern. In: Proc. of ECAI 2004, pp. 171–175 (2004)
Smith, B.: Sets of symmetry breaking constraints. In: Proc. of SymCon 2005. (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Law, Y.C., Lee, J.H.M., Walsh, T., Yip, J.Y.K. (2007). Breaking Symmetry of Interchangeable Variables and Values. In: Bessière, C. (eds) Principles and Practice of Constraint Programming – CP 2007. CP 2007. Lecture Notes in Computer Science, vol 4741. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74970-7_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-74970-7_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74969-1
Online ISBN: 978-3-540-74970-7
eBook Packages: Computer ScienceComputer Science (R0)