Abstract
Many research works on symmetry in CSPs appeared recently. But, most of them deal only with the global symmetry of the studied problem and give no strategy that can be used to detect and eliminate local symmetry. Eliminating global symmetry is shown to be useful, but exploiting only these symmetries could not be sufficient to solve some hard locally symmetrical problems. That is, a problem can have few or no initial symmetries and become very symmetrical at some nodes during the search. In this paper we study a general principle of semantic symmetry and define a syntactic symmetry which is a sufficient condition for semantic symmetry. We define a weakened form of this syntactic symmetry, and show how to detect and how to eliminate it locally to increase CSP tree search methods efficiency. Experiments confirm that local symmetry breaking is profitable for CSP solving.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Krishnamurty, B.: Short proofs for tricky formulas. Acta informatica 22, 253–275 (1985)
Benhamou, B., Sais, L.: Theoretical study of symmetries in propositional calculus and application. In: Eleventh International Conference on Automated Deduction, Saratoga Springs, NY, USA (1992)
Benhamou, B., Sais, L.: Tractability through symmetries in propositional calculus. Journal of Automated Reasoning (JAR) 12, 89–102 (1994)
Benhamou, B., Sais, L., Siegel, P.: Two proof procedures for a cardinality based language. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol. 775, pp. 71–82. Springer, Heidelberg (1994)
Freuder, E.: Eliminating interchangeable values in constraints satisfaction problems. In: Proc AAAI 1991, pp. 227–233 (1991)
Puget, J.F.: On the satisfiability of symmetrical constrained satisfaction problems. In: Komorowski, J., Raś, Z.W. (eds.) ISMIS 1993. LNCS, vol. 689, Springer, Heidelberg (1993)
Benhamou, B.: Study of symmetry in constraint satisfaction problems. In: Borning, A. (ed.) PPCP 1994. LNCS, vol. 874, Springer, Heidelberg (1994)
Crawford, J., Ginsberg, M.L., Luck, E., Roy, A.: Symmetry-breaking predicates for search problems. In: KR 1996. Principles of Knowledge Representation and Reasoning, pp. 148–159. Morgan Kaufmann, San Francisco, California (1996)
Aloul, F.A., Ramani, A., Markov, I.L., Sakallak, K.A.: Solving difficult sat instances in the presence of symmetry. IEEE Transaction on CAD 22(9), 1117–1137 (2003)
Aloul, F.A., Ramani, A., Markov, I.L., Sakallak, K.A.: Symmetry breaking for pseudo-boolean satisfiabilty. In: ASPDAC 2004, pp. 884–887 (2004)
Backofen, R., Will, S.: Excluding symmetries in constraint-based search. In: Jaffar, J. (ed.) Principles and Practice of Constraint Programming – CP 1999. LNCS, vol. 1713, Springer, Heidelberg (1999)
Gent, I.P., Smith, B.M.: Symmetry breaking during search in constraint programming. In: Proceedings ECAI 2000 (2000)
Gent, I., 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)
Focacci, F., Milano, M.: Global cut framework for removing symmetries. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 77–82. Springer, Heidelberg (2001)
Fahle, T., Schamberger, S., Sellmann, M.: Symmetry breaking. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 93–108. Springer, Heidelberg (2001)
Puget, J.: Symmetry breaking revisited. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 446–461. Springer, Heidelberg (2002)
Gent, I.P., Hervey, W., Kesley, T., Linton, S.: Generic sbdd using computational group theory. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833. Springer, Heidelberg (2003)
Roney-Dougal, C.M., Gent, I.P., Kelsey, T., Linton, S.A.: Tractable symmetry breaking using restricted search trees. In: Proceedings of ECAI 2004, pp. 211–215 (2004)
Puget, J.: Breaking symmetries in all diffrent problems. In: Proceedings of IJCAI, pp. 272–277 (2005)
Puget, J.: Breaking all value symmetries in surjection problems. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 490–504. Springer, Heidelberg (2005)
Cohen, D., Jeavons, P., Jefferson, C., Petrie, K., Smith, B.: Symmetry definitions for constraint satisfaction problems. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 17–31. Springer, Heidelberg (2005)
Puget, J.: Dynamic lex constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 453–467. Springer, Heidelberg (2006)
Walsh, T.: General symmetry breaking constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 650–664. Springer, Heidelberg (2006)
Gent, I.P., Kelsey, T., Linton, S.A., McDonald, I., Migeul, I., Smith, B.: Conditional symmetry breaking. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 256–270. Springer, Heidelberg (2005)
Zampelli, S., Deville, Y., Dupont, P.: Symmetry breaking in subgraph pattern matching. In: SymCon 2006, pp. 35–42 (2006)
Jegou, P.: Decomposition of domains based on the micro-structure of finite constraint satisfaction problems. In: Proceedings AAAI 1993 (1993)
Benhamou, B., Saïdi, M.R.: Reasoning by dominance in not-equals binary constraint networks. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 670–674. Springer, Heidelberg (2006)
Benhamou, B., Saïdi, M.R.: Some improvements in symmetry elimination in not-equals binary constraint networks. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 1–7. Springer, Heidelberg (2005)
Haralik, R.M., Elliot, G.L.: Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence 14, 263–313 (1980)
McKay, B.: Practical graph isomorphism. Congr. Numer. 30, 45–87 (1981)
Puget, J.F.: Automatic detection of variable and value symmetries. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 474–488. Springer, Heidelberg (2005)
Mears, C., de la Banda, M.G., Wallace, M.: On implementing symmetry detection. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 1–8. Springer, Heidelberg (2006)
Zampelli, S., Deville, Y., Saïdi, M.R., Benhamou, B., Dupont, P.: Breaking local symmetries in subgraph pattern matching. In: The International Symmetry Conference (ISC 2007), Edinburgh, SCOTLAND (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Benhamou, B., Saïdi, M.R. (2007). Local Symmetry Breaking During Search in CSPs. 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_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-74970-7_16
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)