TY - GEN
T1 - Constraint symmetry for the soft CSP
AU - Smith, Barbara M.
AU - Bistarelli, Stefano
AU - O'Sullivan, Barry
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/38149069078
U2 - 10.1007/978-3-540-74970-7_66
DO - 10.1007/978-3-540-74970-7_66
M3 - Conference proceeding
AN - SCOPUS:38149069078
SN - 3540749691
SN - 9783540749691
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 872
EP - 879
BT - Principles and Practice of Constraint Programming - CP 2007 - 13th International Conference, CP 2007, Proceedings
PB - Springer Verlag
T2 - 13th International Conference on Principles and Practice of Constraint Programming, CP 2007
Y2 - 23 September 2007 through 27 September 2007
ER -