×

zbMATH — the first resource for mathematics

Dynamic structural symmetry breaking for constraint satisfaction problems. (English) Zbl 1186.68438
Summary: In recent years, symmetry breaking for constraint satisfaction problems (CSPs) has attracted considerable attention. Various general schemes have been proposed to eliminate symmetries. In general, these schemes may take exponential space or time to eliminate all the symmetries. We identify several classes of CSPs that encompass many practical problems and for which symmetry breaking for various forms of value or variable interchangeability is tractable using dedicated search procedures. We also show the limits of efficient symmetry breaking for such dominance-detection schemes by proving intractability results for some classes of CSPs.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
OPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja, R., Magnati, T., & Orlin, J. (1993). Network flows. Englewood Cliffs: Prentice Hall.
[2] Backofen, R., & Will, S. (1999). Excluding symmetries in constraint-based search. In J. Jaffar (Ed.), Proceedings of CP’99, LNCS (Vol. 1713, pp. 73–87). New York: Springer. · Zbl 0957.68103
[3] Barnier, N., & Brisset, P. (2002). Solving the Kirkman’s schoolgirl problem in a few seconds. In P. Van Hentenryck (Ed.), Proceedings of CP’02, LNCS (Vol. 2470. pp. 477–491). New York: Springer. · Zbl 1112.90064
[4] Cameron, P. (1999). Permutation groups. Number 45 in London Mathematical Society Student Texts. Cambridge: Cambridge University Press.
[5] Cohen, D. A., Jeavons, P., Jefferson, C., Petrie, K. E., & Smith, B. M. (2005). Symmetry definitions for constraint satisfaction problems. In P. van Beek (Ed.) Proceedings of CP’05, LNCS (Vol. 3709, pp. 17–31). New York: Springer. · Zbl 1153.68454
[6] Colbourn, C. J., & Dinitz, J. H. (Eds.) (1996). The CRC handbook of combinatorial designs. Boca Raton: CRC. · Zbl 0836.00010
[7] Crawford, J. M., Ginsberg, M., Luks, E., & Roy, A. (1996). Symmetry-breaking predicates for search problems. In L. C. Aiello, J. Doyle, & S. C. Shapiro (Eds.), Proceedings of KR’96 (pp. 148–159). San Francisco: Morgan Kaufmann.
[8] Er, M. C. (1988). A fast algorithm for generating set partitions. The Computer Journal, 31(3), 283–284. · Zbl 0647.68071 · doi:10.1093/comjnl/31.3.283
[9] Fahle, T., Schamberger, S., & Sellmann, M. (2001). Symmetry breaking. In T. Walsh (Ed.), Proceedings of CP’01, LNCS (Vol. 2239, pp. 93–107). New York: Springer. · Zbl 1067.68631
[10] Flener, P., Frisch, A. M., Hnich, B., Kızıltan, Z., Miguel, I., Pearson, J., et al. (2001). Symmetry in matrix models. In P. Flener & J. Pearson (Eds.), Proceedings of SymCon’01. http://www.it.uu.se/research/group/astra/SymCon01/ .
[11] Flener, P., Frisch, A. M., Hnich, B., Kızıltan, Z., Miguel, I., Pearson, J., et al. (2002). Breaking row and column symmetries in matrix models. In P. Van Hentenryck (Ed.), Proceedings of CP’02, LNCS (Vol. 2470, pp. 462–476). New York: Springer.
[12] Flener, P., Pearson, J., Sellmann, M., & Van Hentenryck, P. (2006). Static and dynamic structural symmetry breaking. In F. Benhamou (Ed.), Proceedings of CP’06, LNCS (Vol. 4204, pp. 695–699). New York: Springer.
[13] Flener, P., Pearson, J., & Sellmann, M. (2008). Static and dynamic structural symmetry breaking. Technical Report 2008-023, Department of Information Technology, Uppsala University, Sweden, September. http://www.it.uu.se/research/reports/2008-023/ . · Zbl 1205.68374
[14] Flener, P., Pearson, J., Sellmann, M., & Ågren, M. (2007). Structural symmetry breaking for constraint satisfaction problems. Technical Report 2007-032, Department of Information Technology, Uppsala University, Sweden, November. http://www.it.uu.se/research/reports/2007-032/ . · Zbl 1186.68438
[15] Focacci, F., & Milano, M. (2001). Global cut framework for removing symmetries. In T. Walsh (Ed.), Proceedings of CP’01, LNCS (Vol. 2239, pp. 77–92). New York: Springer. · Zbl 1067.68633
[16] Freuder, E. C. (1991). Eliminating interchangeable values in constraint satisfaction problems. In Proceedings of AAAI’91 (pp. 227–233). Menlo Park: AAAI.
[17] Gent, I. P., & Smith, B. M. (2000). Symmetry breaking during search in constraint programming. In Proceedings of ECAI’00 (pp. 599–603). Amsterdam: IOS.
[18] Heller, D. S., & Sellmann, M. (2006). Dynamic symmetry breaking restarted. In F. Benhamou (Ed.), Proceedings of CP’06, LNCS (Vol. 4204, pp. 721–725). New York: Springer.
[19] Kubale, M., & Jackowski, B. (1985). A generalized implicit enumeration algorithm for graph coloring. CACM, 28(4), 412–418.
[20] Law, Y., & Lee, J. (2006). Symmetry breaking constraints for value symmetries in constraint satisfaction. Constraints, 11(2–3), 221–267. · Zbl 1103.68813 · doi:10.1007/s10601-006-7095-8
[21] Law, Y., Lee, J., Walsh, T., & Yip, J. (2007). Breaking symmetry of interchangeable variables and values. In C. Bessière (Ed.), Proceedings of CP’07, LNCS (Vol. 4741, pp. 423–437). New York: Springer. · Zbl 1145.68521
[22] Meseguer, P., & Torras, C. (2001). Exploiting symmetries within constraint satisfaction search. Artificial Intelligence, 129(1–2), 133–163. · Zbl 0971.68144 · doi:10.1016/S0004-3702(01)00104-7
[23] Puget, J.-F. (1993). On the satisfiability of symmetrical constrained satisfaction problems. In J. Komorowski & Z. Raś (Ed.), Proceedings of ISMIS’93, LNAI (Vol. 689, pp. 350–361). New York: Springer.
[24] Puget, J.-F. (2002). Symmetry breaking revisited. In P. Van Hentenryck (Ed.), Proceedings of CP’02, LNCS (Vol. 2470, pp. 446–461). New York: Springer.
[25] Puget, J.-F. (2006). An efficient way of breaking value symmetries. In Proceedings of AAAI’06. Menlo Park: AAAI.
[26] Roney-Dougal, C. M., Gent, I. P., Kelsey, T., & Linton, S. (2004). Tractable symmetry breaking using restricted search trees. In R. L. de Mántaras & L. Saitta (Eds.), Proceedings of ECAI’04 (pp. 211–215). Amsterdam: IOS. · Zbl 1109.68613
[27] Sellmann, M., & Van Hentenryck, P. (2005). Structural symmetry breaking. In Proceedings of IJCAI’05 (pp. 298–303). IJCAI.
[28] Sellmann, M., Gellermann, T., & Wright, R. (2007). Cost-based filtering for shorter path constraints. Constraints, 12(2), 207–238. · Zbl 1141.68055 · doi:10.1007/s10601-006-9006-4
[29] Shlyakhter, I. (2001). Generating effective symmetry-breaking predicates for search problems. Electronic Notes in Discrete Mathematics (Vol. 9). Proceedings of SAT’01. · Zbl 1158.68497
[30] Smith, B. M. (2001). Reducing symmetry in a combinatorial design problem. In C. Gervet & M. Wallace (Eds.), Proceedings of CP-AI-OR’01.
[31] Smith, B. M., Brailsford, S. C., Hubbard, P. M., & Williams, H. P. (1996). The progressive party problem: Integer linear programming and constraint programming compared. Constraints, 1, 119–138. · Zbl 05475104 · doi:10.1007/BF00143880
[32] Van Hentenryck, P. (2002). Constraint and integer programming in OPL. INFORMS Journal on Computing, 14(4), 345–372. · Zbl 1238.90102 · doi:10.1287/ijoc.14.4.345.2826
[33] Van Hentenryck, P., Flener, P., Pearson, J., & Ågren, M. (2003). Tractable symmetry breaking for CSPs with interchangeable values. In Proceedings of IJCAI’03 (pp. 277–282). San Francisco: Morgan Kaufmann.
[34] Van Hentenryck, P., Flener, P., Pearson, J., & Ågren, M. (2005). Compositional derivation of symmetries for constraint satisfaction. In J.-D. Zucker & L. Saitta (Eds.), Proceedings of SARA’05, LNAI (Vol. 3607, pp. 234–247). New York: Springer.
[35] Walsh, T. (2007). Breaking value symmetry. In C. Bessière (Ed.), Proceedings of CP’07, LNCS (Vol. 4741, pp. 880–887). New York: Springer.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.