An Efficient Way of Breaking Value Symmetries

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Constraint Satisfaction and Satisfiability

Several methods for breaking value symmetries have been proposed recently in the constraint programming community. They can be used in conjunction with variable symmetry breaking methods. However, this combination does not break all symmetries in general. We present a combination of lex constraints and element constraints that can be used to break all combinations of variable and value symmetries. It is the first time to our knowledge that it is possible to break all combinations of value and variable symmetries by adding constraints. This method is quite efficient when the number of symmetries is not too large, as shown by experiments using graceful graph problems. We also present a new global constraint that deals with the case where there are too many value symmetries. Experiments show that this is highly effective.