We can break symmetry by eliminating solutions within a symmetry class that
are not least in the lexicographical ordering. This is often referred to as the
lex-leader method. Unfortunately, as symmetry groups can be large, the
lexleader method is not tractable in general. We prove that using other total
orderings besides the usual lexicographical ordering will not reduce the
computational complexity of breaking symmetry in general. It follows that
breaking symmetry with other orderings like the Gray code ordering or the
Snake-Lex ordering is intractable in general.

通过消除对称类中不符合词典顺序的解，我们可以打破对称性，但是这种词典 - 领袖法一般情况下很难处理。我们证明在一般情况下使用其他总序关系 (例如格雷码排序或蛇形 - 词典排序) 来打破对称性的计算复杂度是高的。

破解对称性的复杂性

On the Complexity of Breaking Symmetry

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.

该研究论文探讨了如何打破对称问题，介绍了 Lex-Leader 方法和两种替代方法（Gray code 排序和 Snake-Lex 排序），同时发现使用其他排序方式可以更好地对齐目标函数和分支启发式。