Partial symmetry breaking by local search in the group
Tóm tắt
The presence of symmetry in constraint satisfaction problems can cause a great deal of wasted search effort, and several methods for breaking symmetries have been reported. In this paper we describe a new method called Symmetry Breaking by Nonstationary Optimisation, which interleaves local search in the symmetry group with backtrack search on the constraint problem. It can be tuned to break each symmetry with an arbitrarily high probability with high runtime overhead, or as a lightweight but still powerful method with low runtime overhead. It has negligible memory requirement, it combines well with static lex-leader constraints, and its benefit increases with problem hardness.
Tài liệu tham khảo
Apt, K. R., & Wallace, M. G. (2007). Constraint logic programming using eclipse. Cambridge University Press.
Backofen, R., & Will, S. (1999). Excluding symmetries in constraint-based search. In 5th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 1713, pp. 73–87). Springer.
Brown, C. A., Finkelstein, & Purdom, P. W. (1988) Backtrack searching in the presence of symmetry. In Applied algebra, algebraic algorithms and error-correcting codes. Lecture notes in computer science (Vol. 357, pp. 99–110). Springer.
Cohen, D., Jeavons, P., Jefferson, C., Petrie, K. E., & Smith, B. M. (2006). Symmetry definitions for constraint satisfaction problems. Constraints, 11, 115–137.
Crawford, J., Ginsberg, M. L., Luks, E., & Roy, A. (1996). Symmetry-breaking predicates for search problems. In Principles of knowledge representation and reasoning (pp. 148–159). Morgan Kaufmann.
Flener, P., Frisch, A. M., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., et al. (2002). Breaking row and column symmetries in matrix models. In 8th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 2470, pp. 462–476). Springer.
Focacci, F., & Milano, M. (2001). Global cut framework for removing symmetries. In 7th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 2239, pp. 77–92). Springer.
Frisch, A. M., & Harvey, W. (2003). Constraints for breaking all row and column symmetries in a three-by-two matrix. In 3rd international workshop on symmetry in constraint satisfaction problems.
Gent, I. P., Harvey, W., & Kelsey, T. (2002). Groups and constraints: Symmetry breaking during search. In 8th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 2470, pp. 415–430). Springer.
Gent, I. P., Harvey, W., Kelsey, T., & Linton, S. (2003). Generic sbdd using computational group theory. In 9th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 2833, pp. 333–347). Springer.
Gent, I. P., Jefferson, C., & Miguel, I. (2006). Minion: A fast, scalable, constraint solver. In 17th European conference on artificial intelligence (pp. 98–102).
Gent, I. P., McKay, P., Miguel, I., Nightingale, P., & Huczynska, S. (2009). Modelling equidistant frequency permutation arrays in constraints. In 8th symposium on abstraction, reformulation, and approximation.
Gent, I. P., Petrie, K. E., & Puget, J.-F. (2006). Handbook of constraint programming, chapter symmetry in constraint programming (pp. 329–376). Elsevier.
Gent, I. P., & Smith, B. M. (2000). Symmetry breaking in constraint programming. In 14th European conference on artificial intelligence (pp. 599–603).
Grayland, A., Miguel, I., & Roney-Dougal, C. M. (2009). Snake lex: An alternative to double lex. In 15th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 5732, pp. 391–399). Springer.
Harvey, W. (2001). Symmetry breaking and the social golfer problem. In Workshop on symmetry in constraints.
Hnich, B., Prestwich, S. D., Selensky, E., & Smith, B. M. (2006). Constraint models for the covering test problem. Constraints, 11(3), 199–219.
Holt, D. F., Eick, B., & O’Brien, E. A. (2005). Handbook of computational group theory. Chapman & Hall/CRC.
Hoos, H. H., & Stützle, T. (2004). Stochastic local search: Foundations and applications. Morgan Kaufmann.
ILOG, S. A. (2003). ILOG solver 6.0: Reference manual. France: Gentilly.
Katsirelos, G., Narodytska, N., & Walsh, T. (2009) On the complexity and completeness of static constraints for breaking row and column symmetry. In 16th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 6308, pp. 305–320). Springer.
Kelsey, T., Jefferson, C., Petrie, K., & Linton, S. (2006). Gaplex: Generalised static symmetry breaking. In 6th international workshop on symmetry breaking (pp. 17–23). France: Nantes.
Law, Y. C., & Lee, J. H. M. (2006). Symmetry breaking constraints for value symmetries in constraint satisfaction. Constraints, 11, 221–267.
Luks, E., & Roy, A. (2004). The complexity of symmetry-breaking formulas. Annals of Mathematics and Artificial Intelligence, 41(1), 19–45.
McDonald, I., & Smith, B. (2002). Partial symmetry breaking. In 8th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 2470, pp. 207–213). Springer.
Petrie, K. E., & Smith, B. M. (2003). Symmetry breaking in graceful graphs. Technical Report APES-56a-2003, APES Research Group.
Prestwich, S. D., Hnich, B., Rossi, R., & Tarim, S. A. (2008). Symmetry breaking by metaheuristic search. In 8th international workshop on symmetry and constraint satisfaction problems.
Prestwich, S. D., Hnich, B., Rossi, R., & Tarim, S. A. (2008). Symmetry breaking by nonstationary optimisation. In 19th Irish conference on artificial intelligence and cognitive science.
Prestwich, S. D., Hnich, B., Rossi, R., & Tarim, S. A. (2009). Boosting partial symmetry breaking by local search. In 9th international workshop on symmetry and constraint satisfaction problems.
Puget, J.-F. (1993). On the satisfiability of symmetrical constraint satisfaction problems. In Methodologies for intelligent systems. Lecture notes in artificial intelligence (Vol. 689, pp. 350–361). Springer.
Puget, J.-F. (2003). Symmetry breaking using stabilizers. In 9th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 2833, pp. 585–599). Springer.
Puget, J.-F. (2005). Symmetry breaking revisited. Constraints, 10(1), 23–46.
Puget, J.-F. (2006). Dynamic lex constraints. In 12th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 4204, pp. 453–467). Springer.
Puget, J.-F. (2006). An efficient way of breaking value symmetries. In 21st National conference on artificial intelligence (pp. 117–122). Stanford, California:AAAI Press/The MIT Press.
Sadler, A., & Gervet, C. (2008). Enhancing set constraint solvers with lexicographic bounds. Journal of Heuristics, 14(1), 23–67.
Sellmann, M., & van Hentenryck, P. (2005). Structural symmetry breaking. In 19th international joint conference on artificial intelligence (pp. 298–303). Scotland, UK: Edinburgh.
Smith, B. M. (2001). Reducing symmetry in a combinatorial design problem. In International workshop on integration of AI and OR techniques in constraint programming for combinatorial optimization problems.
The GAP Group. (2008). GAP—groups, algorithms, and programming, Version 4.4.12.
Fahle, T., Schamberger, S., & Sellmann, M. (2001). Symmetry breaking. In 7th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 2239, pp. 93–107). Springer.
Walsh, T. (2006). General symmetry breaking constraints. In 12th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 4204, pp. 650–664). Springer.
Yip, J., & van Hentenryck, P. (2009). The evaluation of length-lex set variables. In 15th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 5732, pp. 817–832). Springer.