# Symmetries Of Symmetry Breaking Constraints

George Katsirelos1and **Toby Walsh**2 Abstract. Symmetry is an important feature of many constraint programs. We show that any problem symmetry acting on a set of symmetry breaking constraints can be used to break symmetry. Different symmetries pick out different solutions in each symmetry class. This simple but powerful idea can be used in a number of different ways.

We describe one application within model restarts, a search technique designed to reduce the conflict between symmetry breaking and the branching heuristic. In model restarts, we restart search periodically with a random symmetry of the symmetry breaking constraints. Experimental results show that this symmetry breaking technique is effective in practice on some standard benchmark problems.

## 1 Introduction

Symmetry occurs in many real world problems. For instance, certain machines in a scheduling problem might be identical. If we have a valid schedule, we can permute these machines and still have a valid schedule. We typically need to factor such symmetry out of the search space to be able to find solutions efficiently. One popular way to deal with symmetry is to add constraints which eliminate symmetric solutions (see, for instance, [15, 18, 4, 14, 19, 21]). Such symmetry breaking is usually simple to implement [5, 6] and is often highly efficient and effective in practice. Even for problems with many symmetries, a small number of symmetry breaking constraints can often eliminate much or all of the symmetry. But where do such symmetry breaking constraints come from? We show here that we can apply symmetry to symmetry breaking constraints themselves to generate potentially new symmetry breaking constraints.

There are a number of applications of this simple but powerful idea. We give one application in the area of restart based methods. Restarting has proven a powerful technique to deal with branching mistakes in backtracking search [9]. One problem with posting symmetry breaking constraints is that they pick out particular solutions in each symmetry class, and branching heuristics may conflict with this choice. *Model restarts* is a technique to deal with this conflict [10].

We periodically restart search with a new model containing different symmetry breaking constraints. Our idea of applying symmetry to symmetry breaking constraints provides a systematic method to generate different symmetry breaking constraints to be used within model restarts. Different symmetries pick out different solutions in each symmetry class. Restarting search with a different symmetry of the symmetry breaking constraints may therefore permit symmetry breaking constraints to be posted that do not conflict with the branching heuristic. Our experimental results show that model restarts is indeed effective at reducing the conflict between branching heuristics and symmetry breaking.

1 CRIL-CNRS, Lens, France, email: gkatsi@gmail.com 2 NICTA and UNSW, Sydney, Australia, email: toby.walsh@nicta.com.au

## 2 Symmetry

We consider two common types of symmetry (see [1] for more discussion). A *variable symmetry* is a permutation of the variables that preserves solutions. Formally, a variable symmetry is a bijection σ on the indices of variables such that if X1 = d1**, . . . , X**n = dn is a solution then Xσ(1) = d1**, . . . , X**σ(n) = dn is also. A *value symmetry* is a permutation of the values that preserves solutions. Formally, a value symmetry is a bijection θ on the values such that if X1 =
d1**, . . . , X**n = dn is a solution then X1 = θ(d1)**, . . . , X**n = θ(dn)
is also. In [17], these are called *global value symmetries* as their action on values is the same for all variables. Symmetries can more generally act on both variables and values. Our results apply also to such symmetries. As the inverse of a symmetry and the identity are symmetries, the set of symmetries forms a group under composition.

We will use a simple running example which has a small number of symmetries. This example will demonstrate that we can use symmetry itself to pick out different solutions in each symmetry class.

Running Example. A magic square is a labelling of a n by n square with the numbers 1 to n 2*so that the sums of each row, column and* diagonal are equal (prob019 in CSPLib [8]). The most-perfect magic square problem is to find a magic square in which every 2 by 2 square has the same sum, and in which all pairs of integers n/2 apart on either diagonal have the same sum. We model this as a CSP with Xi,j = k *iff the square* (**i, j**) contains k*. One solution for* n = 4 is:

![0_image_0.png](0_image_0.png)

$$(1)$$

This is one of the oldest known most-perfect magic squares, dating from a 10th century temple engraving in Khajuraho, India.

This problem has several symmetries. First, there are the 8 symmetries of the square: the identity mapping, the rotations 90◦*clockwise,*
180◦and 270◦, and the reflections in the vertical, horizontal and diagonal axes. For example, applying the symmetry σv that reflects the square in its vertical axis to (1) gives a symmetric solution:

![0_image_1.png](0_image_1.png)

$${\mathrm{(2)}}$$

The problem also has a value symmetry θinv *that inverts values,*
mapping i *onto* n 2 + 1 − i*. For instance, applying* θinv *to (1), generates another symmetric solution:*

![0_image_2.png](0_image_2.png)

$$\mathbf{\Sigma}^{(3)}$$
