  We can break symmetry by eliminating solutions within each symmetry class.
For instance, the Lex-Leader method eliminates all but the smallest solution in
the lexicographical ordering. Unfortunately, the Lex-Leader method is
intractable in general. We prove that, under modest assumptions, we cannot
reduce the worst case complexity of breaking symmetry by using other orderings
on solutions. We also prove that a common type of symmetry, where rows and
columns in a matrix of decision variables are interchangeable, is intractable
to break when we use two promising alternatives to the lexicographical
ordering: the Gray code ordering (which uses a different ordering on
solutions), and the Snake-Lex ordering (which is a variant of the
lexicographical ordering that re-orders the variables). Nevertheless, we show
experimentally that using other orderings like the Gray code to break symmetry
can be beneficial in practice as they may better align with the objective
function and branching heuristic.
