# Breaking Value Symmetry∗

Toby Walsh NICTA and UNSW
Sydney, Australia toby.walsh@nicta.com.au

## Abstract

Symmetry is an important factor in solving many constraint satisfaction problems. One common type of symmetry is when we have symmetric values. In a recent series of papers, we have studied methods to break value symmetries
(Walsh 2006a; Walsh 2007). Our results identify computational limits on eliminating value symmetry. For instance, we prove that pruning all symmetric values is NP-hard in general.

Nevertheless, experiments show that much value symmetry can be broken in practice. These results may be useful to researchers in planning, scheduling and other areas as value symmetry occurs in many different domains.

## Introduction

Many search problems contain symmetries. Symmetry occurs naturally in many problems (e.g. if we have identical machines to schedule, identical jobs to process, or equivalently skilled personnel to roster). Symmetry can also be introduced when we model a problem (e.g. if we name the elements in a set, we introduce the possibility of permuting their order). Unfortunately, symmetries increases the size of the search space. If we do not eliminate symmetries, we will waste much time visiting symmetric solutions, as well as those parts of the search tree which are symmetric to already visited states.

One common type of symmetry is when values are symmetric. For example, if we are assigning colors (values) to nodes (variables) in a graph coloring problem, we can uniformly swap the names of the colors throughout a coloring.

As a second example if we are assigning nurses (values) to shifts (variables) in a rostering problems, and two nurses have the same skills, we may be able to interchange them uniformly throughout the schedule. In a recent series of papers (Walsh 2006a; Walsh 2007), we have studied methods to eliminate such value symmetries. A clear picture of breaking value symmetry is emerging from these studies. These results may be useful to researchers in other areas of AI as value symmetry is a common feature of many domains.

∗The author is funded by the Australian Government's Department of Broadband, Communications and the Digital Economy and the Australian Research Council.

Copyright c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

## An Example

To illustrate the ideas, we consider a simple problem from musical composition. The all interval series problem
(prob007 in CSPLib.org) asks for a permutation of the numbers 0 to n − 1 so that neighbouring differences form a permutation of 1 to n−1. For n = 12, the problem corresponds to arranging the half-notes of a scale so that all musical intervals (minor second to major seventh) are covered. This is a simple example of a graceful graph problem in which the graph is a path.

We can model this as a constraint satisfaction problem in n variables with Xi = j iff the ith number in the series is j.

One solution for n = 11 is:
X1, X2**, . . . , X**11 = 3, 7, 4, 6, 5, 0, 10, 1, 9, 2, 8 (1)
The all interval series problem has a number of different symmetries. First, we can reverse any solution and generate a new (but symmetric) solution:
X1, X2**, . . . , X**11 = 8, 2, 9, 1, 10, 0, 5, 6, 4, 7, 3 (2)
Second, the all interval series problem has a value symmetry as we can invert values. If we subtract all values in (1) from 10, we generate a second (but symmetric) solution:
X1, X2**, . . . , X**11 = 7, 3, 6, 4, 5, 10, 0, 9, 1, 8, 2 (3)
Third, we can do both and generate a third (but symmetric) solution:
X1, X2**, . . . , X**11 = 2, 8, 1, 9, 0, 10, 5, 4, 6, 3, 7 (4)
To eliminate such symmetric solutions from the search space, we can post additional constraints which eliminate all but one solution in each symmetry class. To eliminate the reversal of a solution, we can simply post the constraint:
X1 < X11 (5)
This eliminates solution (2) as it is a reversal of (1).

To eliminate the value symmetry which subtracts all values from 10, we can post:
X1 ≤ 10 − X1, X1 = 10 − X1 ⇒ X2 < 10 − X2 (6)
This is equivalent to:

$$X_{1}=5\Rightarrow X_{2}<5$$
$$X_{1}\leq5,$$
X1 ≤ 5, X1 = 5 ⇒ X2 < 5