# A Partial Taxonomy Of Substitutability And Interchangeability

Shant Karakashian 1, Robert Woodward 1, Berthe Y. Choueiry 1, Steven D.

Prestwich 2 and Eugene C. Freuder 2 1 Constraint Systems Laboratory, University of Nebraska-Lincoln, USA {shantk,rwoodwar,choueiry}@cse.unl.edu 2 Cork Constraint Computation Centre, Department of Computer Science, University College Cork, Ireland{s.prestwich,e.freuder}@4c.ucc.ie Abstract. Substitutability, interchangeability and related concepts in Constraint Programming were introduced approximately twenty years ago and have given rise to considerable subsequent research. We survey this work, classify, and relate the different concepts, and indicate directions for future work, in particular with respect to making connections with research into symmetry breaking. This paper is a condensed version of a larger work in progress.

## 1 Introduction

Many important problems in computer science, engineering and management can be formulated as Constraint Satisfaction Problems (CSPs). A CSP is a triple (*V, D, C*) whereV is a set of variables,D the set of their domain values, andC a set of constraints on the variables that specify the permitted or forbidden combinations of value assignment to variables. A solution to a CSP is an assignment of values to all variables such that all constraints are satisfied. CSPs are usually solved by interleaving backtrack search with some form of constraint propagation, for example forward checking or arc consistency.

Constraint problems often exhibit symmetries. A great deal of research has been devoted to *symmetry breaking* techniques in order to reduce the size of the search space[Various, 1991 present]. The earliest works on symmetry breaking include[Glaisher, 1874; Brown *et al.*, 1988]. In this paper we will not survey the large literature on symmetry breaking, but a recent survey can be found in [Gent *et al.*, 2006].

Interchangeability, proposed in a seminal paper by Freuder[1991], is one of the first forms of symmetry identified for CSPs. Importantly, it is also the first method proposed for *detecting* symmetry as opposed to having a constraint programmer manually specify it. Although there has been since then a steady flow of research papers developing this concept in both theory and practice, it has been relatively neglected compared to other forms of symmetry. This situation is surprising: While in its basic form, interchangeability is a special case of value symmetry, its various extensions (already proposed in the 1991 paper) make