id: 05318831
dt: a
an: 05318831
au: Law, Y.C.; Lee, J.H.M.; Walsh, Toby; Yip, J.Y.K.
ti: Breaking symmetry of interchangeable variables and values.
so: Bessière, Christian (ed.), Principles and practice of constraint
    programming ‒ CP 2007. 13th international conference, CP 2007,
    Providence, RI, USA, September 23‒27, 2007. Proceedings. Berlin:
    Springer (ISBN 978-3-540-74969-1/pbk). Lecture Notes in Computer
    Science 4741, 423-437 (2007).
py: 2007
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-540-74970-7_31
ab: Summary: A common type of symmetry is when both variables and values
    partition into interchangeable sets. Polynomial methods have been
    introduced to eliminate all symmetric solutions introduced by such
    interchangeability. Unfortunately, whilst eliminating all symmetric
    solutions is tractable in this case, pruning all symmetric values is
    NP-hard. We introduce a new global constraint called SigLex and its GAC
    propagator for pruning some (but not necessarily all) symmetric values.
    We also investigate how different postings of the SigLex constraints
    affect the pruning performance during constraint solving. Finally, we
    test these static symmetry breaking constraints experimentally for the
    first time.
rv: