Static Symmetry Breaking with the Reflex Ordering

Abstract

LexLeader, a state of the art static symmetry breaking method, adds a lex ordering constraint for each variable symmetry of the problem to select the lexicographically least solution. In practice, the same method can also be used for partial symmetry breaking by breaking only a given subset of symmetries. We propose a new total ordering, reflex, as basis of a new symmetry breaking constraint that collaborates well among themselves as well as with Precedence constraints, thereby breaking more composition symmetries in partial symmetry breaking. An efficient GAC filtering algorithm is presented for the reflex ordering constraint. We propose the ReflexLeader method, which is a variant of LexLeader using the reflex ordering instead, and give conditions when ReflexLeader is safe to combine with the Precedence and multiset ordering constraints. Extensive experimentations demonstrate empirically our claims and substantial advantages of the reflex ordering over the lex ordering in partial symmetry breaking.