Symmetry Breaking
A symmetry is a transformation of an entity which preserves the properties of the entity. The transformed entity is thus identical to and indistinguishable from the original entity. For instance, rotating a chess board 180 degrees gives us a board which is indistinguishable from the original board.
Many constraint satisfaction problems (CSPs) have symmetries in the variables, domains or constraints - or any combination thereof. Each of these symmetries preserve satisfiability, so that when there is symmetry in a CSP, any assignment can be transformed into an equivalent assignment without affecting whether or not it satisfies the constraints.
Symmetry can have an enormous effect on the combinatorial complexity of CSPs. In the presence of symmetry, a constraint solver may waste an exorbitant amount of time considering symmetric but equivalent assignments or partial assignments. Hence, dealing with symmetry is often crucial to the success of solving such CSPs efficiently.
Project status: Active
People
| Meinolf Sellmann |
Publications
Flener, P., Pearson, J., Sellmann, M., and Van Hentenryck, P. Static and Dynamic Structural Symmetry Breaking. In Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming (CP) (Nantes, France, Sep 2006), Springer, pp. 695-699. [ pdf ]
Sellmann, M., and Hentenryck, P. V. Structural Symmetry Breaking. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI) (2005), pp. 298-303. [ postscript | pdf ]
Fahle, T., Schamberger, S., and Sellmann, M. Symmetry Breaking. In Proceedings of the Seventh International Conference on the Principles and Practice of Constraint Programming (CP) (2001), Springer, pp. 93-107. [ postscript | pdf ]
| Page Owner: Webmaster | Last Modified: Mon Oct 23 14:57:09 2006 |