it a more general concept than is sometimes perceived, and anticipate some subsequent developments in symmetry definition and breaking. The comparison with the various types and definitions of symmetry [Benhamou, 1994; Cohen et al., 2006] will be discussed in the longer version of this paper.

The goal of our endeavor is to analyze the research conducted so far on interchangeability, relate it to symmetry, and identify opportunities for future research. This paper is a work in progress and a first step towards our goal.

Our survey is partial and far from complete and we welcome the feedback of the readers and workshop participants.

The advantages of detecting and exploiting interchangeability have been established on random problems, benchmarks, and real-world applications. In backtrack search, the advantages are mainly the reduction of the search space and the search effort 1, and the attainment of multiple solutions by bundling. In local search, interchangeability is used to locally repair partial solutions [Petcu and Faltings, 2003]. Real-world applications include nurse scheduling [Weil and Heus, 1998] and resource allocation in hospitals [Choueiry *et al.*, 1995].

This paper is structured as follows. In Section 2, we give the definitions of the basic interchangeability concepts and relate them to each other. In Section 3, we discuss forms of conditional interchangeability. In Section 4, we discuss other forms of interchangeability that have appeared in the literature. In Section 5, we relate the various forms of interchangeability. Finally, in Section 6, we list topics that we plan to cover more fully in the expanded version of this paper.

## 2 Basic Interchangeability Concepts

In this section, we review the various forms of interchangeability originally introduced in [Freuder, 1991]. We also include a few new interchangeability concepts that directly relate to the original ones. Full interchangeability, the most basic form of interchangeability, is defined as follows.

Full interchangeability (FI) [Freuder, 1991] A value a for variable v is fully interchangeable with value b iff every solution in which v = a remains a solution when b is substituted for a and vice-versa.

If two values are interchangeable then one of them can be removed from the domain, reducing the size of the problem; alternatively they can be bundled together in a Cartesian product representation of solutions. Figures 1, 2 and 3 show examples of two values a and b that are FI (see below for definition of 3-I
and NSub). In our figures, a small solid circle denotes a value in the domain of the variable represented by the outline circle, and edges link consistent tuples.

Notice that FI is defined 'at the solution level', which means that in order to find all FI values for a given variable, one must account for all constraints and may have to compute all solutions. Thus, FI is a *global* property. In [1994],
Benhamou defines the equivalent notion of 'value symmetry in all solutions' as 1 Most importantly, by factoring out no-goods [Choueiry and Davis, 2002].