Lightweight dynamic symmetry breaking
详细信息 查看全文
- 作者：Christopher Mears (1)
Maria Garcia de la Banda (1)
Bart Demoen (2)
Mark Wallace (1) - 关键词：Symmetry ; Symmetry breaking ; Group theory ; Search
- 刊名：Constraints
- 出版年：2014
- 出版时间：July 2014
- 年：2014
- 卷：19
- 期：3
- 页码：195-242
- 全文大小：
- 参考文献：1. Backofen, R., & Will, S. (1999). Excluding symmetries in constraint-based search. In J. Jaffar (Ed.), / CP. Lecture notes in computer science (Vol. 1713, pp. 73鈥?7). Springer.
2. Cohen, D.A., Jeavons, P., Jefferson, C., Petrie, K.E., Smith, B.M. (2006). Symmetry definitions for constraint satisfaction problems. / Constraints, 11(2鈥?), 115鈥?37. CrossRef
3. Crawford, J.M., Ginsberg, M.L., Luks, E.M., Roy, A. (1996). Symmetry-breaking predicates for search problems. In L.C. Aiello, J. Doyle, S.C. Shapiro (Eds.), / KR (pp. 148鈥?59). Morgan Kaufmann.
4. Fahle, T., Schamberger, S., Sellmann, M. (2001). Symmetry breaking. In T. Walsh (Ed.), / Principles and practice of constraint programming - CP 2001, 7th international conference, CP 2001, Paphos, Cyprus, 26 November鈥? December 2001, proceedings. Lecture notes in computer science (Vol. 2239, pp. 93鈥?07). Springer.
5. Flener, P., Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T. (2002). Breaking row and column symmetries in matrix models. In P. Van Hentenryck (Ed.), / Principles and practice of constraint programming - CP 2002, 8th international conference, CP 2002, Ithaca, NY, USA, 9鈥?3 September 2002, proceedings. Lecture notes in computer science (Vol. 2470, pp. 462鈥?76). Springer.
6. Flener, P., Pearson, J., Sellmann, M. (2009). Static and dynamic structural symmetry breaking. / Annals of Mathematics and Artificial Intelligence, 57(1), 37鈥?7. CrossRef
7. Flener, P., Pearson, J., Sellmann, M., Van Hentenryck, P., 脜gren, M. (2009). Dynamic structural symmetry breaking for constraint satisfaction problems. / Constraints, 14(4), 506鈥?38. CrossRef
8. Focacci, F., & Milano, M. (2001). Global cut framework for removing symmetries. In T. Walsh (Ed.), / Principles and practice of constraint programming - CP 2001, 7th international conference, CP 2001, Paphos, Cyprus, 26 November鈥? December 2001, proceedings. Lecture notes in computer science (Vol. 2239, pp. 77鈥?2). Springer.
9. Gecode Team (2006). Gecode: generic constraint development environment. Available from http://www.gecode.org. Accessed 15 Nov 2013.
10. Gent, I.P., Harvey, W., Kelsey, T. (2002). Groups and constraints: symmetry breaking during search. In P. Van Hentenryck (Ed.), / Principles and practice of constraint programming - CP 2002, 8th international conference, CP 2002, Ithaca, NY, USA, 9鈥?3 September 2002, proceedings. Lecture notes in computer science (Vol. 2470, pp. 415鈥?30). Springer.
11. Gent, I.P., Harvey, W., Kelsey, T., Linton, S. (2003). Generic SBDD using computational group theory. In F. Rossi (Ed.), / Principles and practice of constraint programming - CP 2003, 9th international conference, CP 2003, Kinsale, Ireland, 29 September鈥? October 2003, proceedings. Lecture notes in computer science (Vol. 2833, pp. 333鈥?47). Springer.
12. Gent, I.P., & Smith, B.M. (2000). Symmetry breaking in constraint programming. In W. Horn (Ed.), / ECAI (pp. 599鈥?03). IOS Press.
13. Gent, I.P., & Walsh, T. (1999). / CSPLib: a benchmark library for constraints. Technical report, Technical report APES-09-1999. Available from http://www.csplib.org/. Accessed 15 Nov 2013.
14. Gomes, C.P., Selman, B., Crato, N., Kautz, H.A. (2000). Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. / Journal of Automated Reasoning, 24(1/2), 67鈥?00. CrossRef
15. Heller, D.S., Panda, A., Sellmann, M., Yip, J. (2008). Model restarts for structural symmetry breaking. In P.J. Stuckey (Ed.), / CP. Lecture notes in computer science (Vol. 5202, pp. 539鈥?44). Springer.
16. Law, Y., & Lee, J. (2006). Symmetry breaking constraints for value symmetries in constraint satisfaction. / Constraints, 11(2鈥?), 221鈥?67. CrossRef
17. Law, Y.C., Lee, J.H.M., Walsh, T., Yip, J.Y.K. (2007). Breaking symmetry of interchangeable variables and values. In C. Bessiere (Ed.), / CP. Lecture notes in computer science (Vol. 4741, pp. 423鈥?37). Springer.
18. McDonald, I., & Smith, B.M. (2002). Partial symmetry breaking. In P. Van Hentenryck (Ed.), / Principles and practice of constraint programming - CP 2002, 8th international conference, CP 2002, Ithaca, NY, USA, 9鈥?3 September 2002, proceedings. Lecture notes in computer science (Vol. 2470, pp. 431鈥?45). Springer.
19. Mears, C., Garcia de la Banda, M.., Wallace, M., Demoen, B. (2008). A novel approach for detecting symmetries in CSP models. In L. Perron & M.A. Trick (Eds.), / CPAIOR. Lecture notes in computer science (Vol. 5015, pp. 158鈥?72). Springer.
20. Mears, C., Garcia de la Banda, M., Demoen, B., Wallace, M. (2008). Lightweight dynamic symmetry breaking. In / SymCon鈥?8: The 8th international workshop on symmetry in constraint satisfaction problems.
21. Petrie, K.E., & Smith, B.M. (2003). Symmetry breaking in graceful graphs. In F. Rossi (Ed.), / Principles and practice of constraint programming - CP 2003, 9th international conference, CP 2003, Kinsale, Ireland, 29 September鈥? October 2003, proceedings. Lecture notes in computer science (Vol. 2833, pp. 930鈥?34). Springer.
22. Prestwich, S.D., Hnich, B., Simonis, H., Rossi, R., Tarim, S.A. (2012). Partial symmetry breaking by local search in the group. / Constraints, 17, 148鈥?71. CrossRef
23. Puget, J.-F. (1993). On the satisfiability of symmetrical constrained satisfaction problems. In / Proceedings of the 7th international symposium on methodologies for intelligent systems. ISMIS 鈥?3 (pp. 350鈥?61). London: Springer-Verlag.
24. Puget, J.-F. (2002). Symmetry breaking revisited. In P. Van Hentenryck (Ed.), / Principles and practice of constraint programming - CP 2002, 8th international conference, CP 2002, Ithaca, NY, USA, 9鈥?3 September 2002, proceedings. Lecture notes in computer science (Vol. 2470, pp. 446鈥?61). Springer.
25. Puget, J.-F. (2003). Symmetry breaking using stabilizers. In F. Rossi (Ed.), / Principles and practice of constraint programming - CP 2003, 9th international conference, CP 2003, Kinsale, Ireland, 29 September鈥? October 2003, proceedings. Lecture notes in computer science (Vol. 2833, pp. 585鈥?99). Springer.
26. Roney-Dougal, C.M., Gent, I.P., Kelsey, T., Linton, S. (2004). Tractable symmetry breaking using restricted search trees. In R. L贸pez de M谩ntaras & L. Saitta (Eds.), / ECAI (pp. 211鈥?15). IOS Press.
27. The GAP Group (2006). / GAP 鈥?groups, algorithms, and programming, version 4.4.9.
28. Van Hentenryck, P., Flener, P., Pearson, J., 脜gren, M. (2003). Tractable symmetry breaking for CSPs with interchangeable values. In G. Gottlob & T. Walsh (Eds.), / IJCAI (pp. 277鈥?84). Morgan Kaufmann.
29. Van Hentenryck, P., Flener, P., Pearson, J., 脜gren, M. (2005). Compositional derivation of symmetries for constraint satisfaction. In J.-D. Zucker & L. Saitta (Eds.), / SARA. Lecture notes in computer science (Vol. 3607, pp. 234鈥?47). Springer.
30. Wallace, M.G., Novello, S., Schimpf, J. (1997). ECLiPSe: a platform for constraint logic programming. / ICL Systems Journal, 12(1), 159鈥?00. - 作者单位：Christopher Mears (1)
Maria Garcia de la Banda (1)
Bart Demoen (2)
Mark Wallace (1)
1. Monash University, Caulfield East, Australia
2. KU Leuven, Leuven, Belgium - ISSN：1572-9354
文摘
Symmetries in constraint problems present an opportunity for reducing search. This paper presents Lightweight Dynamic Symmetry Breaking, an automatic symmetry breaking method that is efficient enough to be used as a default, since it never yields a major slowdown while often giving major performance improvements. This is achieved by automatically exploiting certain kinds of symmetry that are common, can be compactly represented, easily and efficiently processed, automatically detected, and lead to large reductions in search. Moreover, the method is easy to implement and integrate in any constraint system. Experimental results show the method is competitive with the best symmetry breaking methods without risking poor performance.