Abstract
There exist various methods to break symmetries. The two that concern us in this paper are static symmetry breaking where we add static constraints to the problem (see e.g. [1,3]) and symmetry breaking by dominance detection (SBDD) where we filter values based on a symmetric dominance analysis when comparing the current searchnode with those that were previously expanded [2,5]. The core task of SBDD is dominance detection. The first provably polynomial-time dominance checkers for value symmetry were devised in [18] and [14]. For problems exhibiting both “piecewise” symmetric values and variables, [15] devised structural symmetry breaking (SSB). SSB is a polynomial-time dominance checker for piecewise symmetries which, used within SBDD, eliminates symmetric subproblems from the search-tree. Piecewise symmetries are of particular interest as they result naturally from symmetry detection based on a static analysis of a given CSP that exploits the knowledge about problem substructures as captured in global constraints [17]. Static SSB was developed in [4] and is based on the structural abstractions that were introduced in [17].
This work was supported by the National Science Foundation through the Career: Cornflower Project (award number 0644113).
This is a preview of subscription content, log in via an institution to check access.
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
Crawford, J., Ginsberg, M., Luks, E., Roy, A.: Symmetry-breaking predicates for search problems. In: KR, pp. 149–159 (1996)
Fahle, T., Schamberger, S., Sellmann, M.: Symmetry Breaking. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 93–107. Springer, Heidelberg (2001)
Flener, P., Frisch, A., 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)
Flener, P., Pearson, J., Sellmann, M., Van Hentenryck, P.: Static and Dynamic Structural Symmetry Breaking. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 695–699. Springer, Heidelberg (2006)
Focacci, F., Milano, M.: Global cut framework for removing symmetries. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 77–92. Springer, Heidelberg (2001)
Gent, I., Harvey, W., Kelsey, T., Linton, S.: Generic SBDD using computational group theory. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 333–347. Springer, Heidelberg (2003)
Gomes, C.P., Selman, B., Crato, N.: Heavy-Tailed Distributions in Combinatorial Search. In: CP, pp. 121–135 (1997)
Heller, D., Sellmann, M.: Dynamic Symmetry Breaking Restarted. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 721–725. Springer, Heidelberg (2006)
Kautz, H., Horvitz, E., Ruan, Y., Gomes, C., Selman, B.: Dynamic Restart Policies. In: AAAI, pp. 674–682 (2002)
Kiziltan, Z.: Symmetry Breaking Ordering Constraints. PhD Thesis (2004)
Law, Y.-C., Lee, J., Walsh, T., Yip, J.: Breaking symmetry of interchangeable variables and values. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 423–437. Springer, Heidelberg (2007)
Puget, J.F.: Dynamic Lex Constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 453–467. Springer, Heidelberg (2006)
Régin, J.-C.: Generalized arc-consistency for global cardinality constraint. In: AAAI, pp. 209–215. AAAI Press, Menlo Park (1996)
Roney-Dougal, C., Gent, I., Kelsey, T., Linton, S.: Tractable symmetry breaking using restricted search trees. In: ECAI, pp. 211–215 (2004)
Sellmann, M., Van Hentenryck, P.: Structural Symmetry Breaking. In: IJCAI, pp. 298–303 (2005)
Smith, B.M.: Sets of Symmetry Breaking Constraints. In: SymCon 2005 (2005)
Van Hentenryck, P., Flener, P., Pearson, J., Agren, M.: Compositional derivation of symmetries for constraint satisfaction. In: Zucker, J.-D., Saitta, L. (eds.) SARA 2005. LNCS (LNAI), vol. 3607, pp. 234–247. Springer, Heidelberg (2005)
Van Hentenryck, P., Flener, P., Pearson, J., Agren, M.: Tractable symmetry breaking for CSPs with interchangeable values. In: IJCAI, pp. 277–282 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Heller, D., Panda, A., Sellmann, M., Yip, J. (2008). Model Restarts for Structural Symmetry Breaking. In: Stuckey, P.J. (eds) Principles and Practice of Constraint Programming. CP 2008. Lecture Notes in Computer Science, vol 5202. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85958-1_38
Download citation
DOI: https://doi.org/10.1007/978-3-540-85958-1_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85957-4
Online ISBN: 978-3-540-85958-1
eBook Packages: Computer ScienceComputer Science (R0)