We introduce a definition of constraint
symmetry for soft CSPs, based on the definition of constraint symmetry for
classical CSPs.
We show that the constraint symmetry group of a soft CSP is a subgroup of that of
an associated classical CSP instance.
Where it is smaller, we can successfully exploit the additional symmetries using
conditional symmetry breaking.
We demonstrate, in a case-study of graph colouring, that eliminating the symmetry of the soft CSP combined with
conditional symmetry breaking can lead to huge reductions in the search effort
to find an optimal solution to the soft CSP.
Back to "Barbara Smith
- Publications on Constraint Programming"