# Symmetry exclusion

### From Glossary

Symmetry exclusion. Excluding
symmetric solutions, usually when solving combinatorial programs. For example, suppose x_{i}j = 1 if item i is
assigned to be at position j (in 2 or 3 dimensional space);
otherwise, x_{i}j=0. When branching on x_{i}j=1,
the alternative optimal value x_ik=1 is being considered for
position k that maps from j under reflection, translation, or
rotation. So, when considering the complementary branch,
x_{i}j=0, the symmetry exclusion condition,
x_{i}k=0, is also added. Symmetry exclusion can sometimes
be done by ordering variables, or with cutting planes. It arises in
most problems with a geometric meaning, including the symmetric
traveling salesman problem, where every tour, (1,2,...,n,1), has the symmetric
solutions (2,3,...,n,1,2) and (1,n,n-1,...,2,1). The first of these
symmetries is excluded by defining city 1 as the first (or "home")
city. Fixing the home does not exclude the second symmetry, which
is a tour reversal. Non-geometric problems can also have
symmetries, such as graph coloring; any coloring has the symmetric
solution by swapping colors – e.g., every red node becomes
green, and every green node becomes red.