Abstract
The addition of symmetry breaking constraints is one of the most successful symmetry breaking technique for constraint satisfaction problems (CSP). In this paper we present STAB, a method that adds some symmetry breaking constraints during the search for solution. STAB adds constraints that are not yet broken by the current partial assignment. The computation of those additional constraints require the computation of graph isomorphism at each node. Graph isomorphism is not know to be NP complete, and in practice can be solved quite efficiently using an auxiliary CSP. The method is refined to be applied to matrix problems where rows and columns can be permuted. A theoretical comparison with previously published methods shows how to combine those methods together safely. An experimental comparison on a class of highly symmetrical combinatorial problems, namely BIBD shows that STAB is more than one order of magnitude more efficient than best published techniques so far.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Backofen, R., Will, S.: Excluding Symmetries in Constraint Based Search. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 73–87. Springer, Heidelberg (1999)
Carlsson, M., Beldiceanu, N.: Revisiting the Lexicographic Ordering Constraint SICS Technical report T2002:17
Crawford, J., Ginsberg, M., Luks, E.M., Roy, A.: Symmetry Breaking Predicates for Search Problems. In: proceedings of KR 1996, pp. 148-159 (1999)
Denny, P.C.: Search and Enumeration Techniques for Incidence Structures. Tech report University of Auckland (1998)
Fahle, T., Shamberger, S., Sellmann, M.: Symmetry Breaking. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 93–107. Springer, Heidelberg (2001)
Flener, P., Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.: Breaking Row and Column Symmetries in Matrix Models. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 462–476. Springer, Heidelberg (2002)
Frisch, M., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Global Constraints for Lexicographic Orderings. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 93–108. Springer, Heidelberg (2002)
Frisch, M., Jefferson, C., Miguel, I.: Constraints for Breaking More Row and Column Symmetries. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 318–332. Springer, Heidelberg (2003)
Focacci, F., Milano, M.: Global Cut Framework for Removing Symmetries. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 75–92. Springer, Heidelberg (2001)
Gent, I.P., Smith, B.M.: Symmetry Breaking During Search in Constraint Programming. In: Proceedings ECAI 2000, pp. 599-603 (2000)
Gent, I.P., Harvey, W., Kelsey, T.: Groups and Constraints: Symmetry Breaking during Search. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 415–430. Springer, Heidelberg (2002)
Meseguer, P., Torras, C.: Exploiting Symmetries Within Constraint Satisfaction Search. Art. Intell. 129, 133–163 (1999)
Puget, J.-F.: On the Satisfiability of Symmetrical Constraint Satisfaction Problems. In: Komorowski, J., Raś, Z.W. (eds.) ISMIS 1993. LNCS, vol. 689, pp. 350–361. Springer, Heidelberg (1993)
Puget, J.-F.: Symmetry Breaking Revisited. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 446–461. Springer, Heidelberg (2002)
Puget, J.-F.: Using Constraint Programming to Compute Symmetries (submitted)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Puget, JF. (2003). Symmetry Breaking Using Stabilizers. In: Rossi, F. (eds) Principles and Practice of Constraint Programming – CP 2003. CP 2003. Lecture Notes in Computer Science, vol 2833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45193-8_40
Download citation
DOI: https://doi.org/10.1007/978-3-540-45193-8_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20202-8
Online ISBN: 978-3-540-45193-8
eBook Packages: Springer Book Archive