Tractable Symmetry Breaking for CSPs with Interchangeable Values

1 Introduction

Symmetry breaking for constraint satisfaction problems has attracted considerable attention in recent years (See the last CP proceedings, the CP'O I and CP'02 workshops on sym­ metries, and [Crawford eta!., 1996; Freuder, 1991; Backofen and Will, 1999; Puget, 1993] for some less recent papers). Indeed, many applications naturally exhibit symmetries and symmetry breaking may drastically improve performance (e.g., [Bamier and Brisset, 2002; Meseguer and Torras, 2001; Puget, 2002]). An important contribution in this area has been the development of various general schemes for symmetry breaking in CSPs (e.g., SBDS [Gent and Smith, 2000] and SBDD [Fahle et al., 2001; Focacci and Milano, 2001]). Un­ fortunately, these schemes, in general, may require exponen­ tial resources to break all symmetries. Indeed, some schemes require exponential space to store all the nogoods generated through symmetries, while others may take exponential time to discover whether a partial assignment is symmetric to one of the existing nogoods. As a consequence, practical applica­ tions often place limits on how many nogoods can be stored

and/or which symmetries to break.

This paper approaches symmetry breaking from a differ­ ent, orthogonal, standpoint. Its goal is to identify classes of CSPs that are practically relevant and for which symmetry breaking is tractable, i.e., symmetry breaking is polynomial in time and space. It identifies several such classes, which P. Flener, J. Pearson, and M. Agren Department of Information Technology Uppsala University, Box 337 S-751 OS Uppsala, Sweden encompass many practical applications. These CSPs fea­ ture various forms of value interchangeability and the paper shows that symmetry breaking can be performed in constant time and space during search using dedicated search proce­ dures. The paper also reports preliminary experimental re­ sults indicating that symmetry breaking on these CSPs brings significant computational benefits. Finally, the paper intro­ duces the new notions of existential and abstract nogoods, which were used to derive the results for the various CSP classes. We believe that these notions are helpful to derive many other classes of tractable symmetries. In particular, they also allowed us to derive classes of tractable variable symmetries, which we cannot include here for space reasons. As such, this paper should be viewed only as a first step in this fascinating area.

It is also useful to contrast our approach with the research avenue pioneered by [Freuder, 1991] on value interchange­ ability. Freuder also introduced various forms of value inter­ changeability. However, his goal was to discover symmetries inside CSPs and to reformulate them by preprocessing to re­ move symmetries. Unfortunately, discovering symmetries in CSPs is not tractable for many interesting classes of CSPs. Our research, in contrast, assumes that modellers are aware of the symmetries in their applications. It focuses on how to exploit this knowledge during search to eliminate symmetries efficiently. Consider, for instance, the scene-shooting prob­ lem featured in [Van Hentenryck, 2002]. This problem aims at producing a movie (or a series) at minimal cost by decid­ ing when to shoot scenes. Each scene involves a number of actors and at most 5 scenes a day can be filmed. All actors of a scene must be present on the day the scene is shot. The ac­ tors have fees representing the amount to be paid per day they spend in the studio. The goal of the application is to minimize the production costs. An optimal solution to this problem can be modelled as an assignment of scenes to days which min­ imizes the production costs. It should be apparent that the exact days assigned to the scenes have no importance in this application and are fully interchangeable. What is important is how the scenes are clustered together. Our approach does not aim at discovering this fact; rather it focuses on how to exploit it to eliminate the symmetries it induces.

The rest of the paper is organized as follows. After some preliminaries, Sections 3, 4, and 5 study three classes ofCSPs for which symmetry breaking is tractable. For space reasons, only the first class is presented in full detail with proofs. Sec­ tion 6 briefly reports some experimental results. Section 7 concludes the paper.

2 Preliminaries

This section defines the main concepts used in this paper. The definitions, although they capture the informal meaning of CSPs, are non-standard and simplify the definitions and proofs considerably. The basic idea is that the set of con­ straints is abstracted by a Boolean function which holds if all the constraints are satisfied (since we are not interested in the constraint structure). Solutions are also represented as func­ tions (assignments) from variables to their sets of values.

Definition 2.1. A CSP is a triplet (V, D, C), where V denotes the set of variables, D denotes the set of possible values for these variables, and C : (V ~ D) ~ Bool is a constraint that specifies which assignments of values to the variables are solutions. A solution to a CSP P = (V, D, C) is a function a : V ~ D such that C(a) =true. The set of solutions to a CSP Pis denoted by Sol(P).

Algorithms to solve CSPs manipulate partial assignments. It is often important to reason about which variables are already assigned (the domain of the partial assignment) and the set of values they are assigned to (the image of the assignment). Note that domains represent sets of variables in this paper (not values as is traditional), since we use functions to model (partial) assignments.

Definition 2.2. Let P = (V, D, C) be a CSP. A partial as­ signment for P is a function a : W ~ V ~ D. The do­ main of a, denoted by dom(a), is W. The image of a, de­ noted by image(a), is the set {a(v) l v E dom(a)}. For each valued E image( a), we use a- (d) to denote the set {v I v E dom(a) 1\ a(v) = d}.

In this paper, we often denote a partial assignment a by a conjunction of equations

where dom(a) = { Vi 1 , · ·· , Vik }. For instance, the partial assignment VI = 1 1\ v2 = 2 1\ V3 = 3 represents the function whose domain is {VI, v2 , v3 } and which assigns the value i to Vi . We also denote the empty assignment by f.. The next four definitions define nogoods formally and when a (partial) assignment violates a nogood.

Definition 2.3. Let P be a CSP and a be a partial assignment for P. A partial assignment (} is an extension of a for P if dom(a) ~ dom(8) and Vv E dom(a) : 8(v) = a(v).

Definition 2.4. Let P = (V, D, C) be a CSP and a be a partial assignment for P . A completion of a for Pis an ex­ tension a' : V ~ D of a for P. The set of all completions of a for Pis denoted by Comp(a, P) .

Definition 2.5. Let P be a CSP. A nogood a for P is a partial assignment for P such that Comp(a, P) n Sol(P) = 0.

Definition 2.6. Let P be a CSP, a be a nogood for P, and 8 be a partial assignment for P. (} violates no good a for P if(} is an extension of a for P.

Proposition 2.7. Let P be a CSP If8 violates nogood a for P, then Comp(8, P) n Sol(P) = 0.

This last proposition shows that nogoods can be lifted from the children to their parent.

Proposition 2.8. Let P = (V, D, C) be a CSP and D = { di, . .. , dm}. Let a be a partial assignment for P with dom(a) = { vit, ... , Vik} and let every a; = a 1\ Vik+ 1 = di (1 ::; i ::; m) be a nogoodfor P. Then a is a nogoodfor P .

3 Value-Interchangeable CSPs

There are many applications in resource allocation and scheduling where the exact values taken by the variables are not important. What is significant is which variables take the same values or, in other terms, how the variables are clus­ tered. This notion of symmetry is what [Freuder, 1991] calls full interchangeability for all variables and all values. The prototypical example is graph-coloring. Another, more com­ plex, example is the scene allocation application mentioned in the introduction. This section shows that symmetry break­ ing for these problems is tractable and takes constant time and space. We first define value-interchangeable CSPs.

Definition 3.1. Let P = (V, D, C) be a CSP. P is value­ interchangeable if, for each solution a E Sol(P) and each bijection b : D ~ D, the function boa E Sol(P).

In the following, we use ICSP as an abbreviation for value­ interchangeable CSP. The following theorem is a fundamental characterization of no goods for ICSPs.

Theorem 3.2. Let P = (V, D, C) be an ICSP, let a be a nogoodfor P, and let b: D ~ D be a bijection. Then boa is a nogood.

The closure of a no good a for an ICSP captures all the "sym­ metric" nogoods that can be obtained from a.

Definition 3.3. Let P = (V, D, C) be an ICSP and a be a no good for P. The closure of a for P, denoted by Closure( a, P), is the set {boa I b: D ~Dis a bijection}.

We now show that the closure of a nogood can be charac­ terized compactly and that membership to the closure of a nogood can be tested in linear time for ICSPs. We first intro­ duce the concept of existential nogood, which simplifies the proofs and intuitions.

Definition 3.4. Let P = (V, D, C) be an ICSP and a be a no good for P. Let image( a) = { d1, ... , dk}. The existen­ tial nogood of a for P, denoted by Enogood(a, P), is the set of all functions 1 : dom (a) ~ D satisfying ·

The following lemma indicates that an existential no good pre­ cisely captures the closure of a no good.

Lemma 3.5. Let P be an ISCP and a be a nogood for P. Then Enogood(a, P) = Closure( a, P) .

Proof Letimage(a) = {d1 , ... ,dk}. Bydefinitionofthe image, we have that

We first show that Closure( a, P) <;;: Enogood(a, P). Let 'Y E Closure( a, P). This means that there exists a bijection b such that 'Y = boa. Thus, 'Y satisfies

by definition of a bijection, and hence 'Y E Enogood(a, P). We now show that Enogood(a, P) <;;: Closure( a, P). Let ~ E Enogood(a, P). There exist some values a1, ... , ak E D such that

Since a1, ... , ak are all different, there exists a bijection b satisfying Vi E l..k : b(d;) = a;. Hence~ can be rewritten as boa and 8 E Closure( a, P). D

It is not obvious that membership to an existential no good can be tested efficiently, since it involves an existential quantifica­ tion. However, due to the nature of the underlying constraints, it is easy to eliminate the existential variables by selecting a representative for each set a -l ( d;). This is precisely the mo­ tivation underlying the concept of abstract nogoods defined below. Consider the existential formula

The variables e1, e2, and e3 can be eliminated to produce

Definition 3.6. Let P = {V, D, C) be an ICSP and a be a nogood for P . Let image(a) = { d1, ... , dk} and let

The abstract nogood of a wrt P, denoted by Anogood(a, P), is the set of functions 'Y : dom(a) -+ D satisfying

Lemma 3.7. Let P be an ICSP and a be a nogoodfor P. Then Enogood(a, P) = Anogood(a, P).

For simplicity, we will often denote the abstract nogood con­ dition in terms of global constraints

where all equal ( i E S) a; holds if all the a; are the same value. It can be seen that there exists a linear time algorithm to test whether a partial assignment B violates a nogood in Closure( a, P). It suffices to test whether B satisfies the for­ mula above whenever dom (a) <;;: dom (B).

Lemma 3.8. Let P be an ICSP. a be a no good for P. and B be a partial assignment. There exists a linear-time algorithm that tests whether B violates any nogood in Closure(a,P) .

Proof Direct consequence oflemmas 3.5 and 3.7 and the fact that the abstract nogood is linear in !VID

Lemma 3.9. Let P = {V, D, C) be an ICSP. D = {dt, ... ,dm}. and a be a partial assignment for P with dom(a) = { v; 1 , ··· , v;k }. Let every a; = a 1\ v;k+l = d; (1::; i::; m) beanogoodforP. Then,

I. a is a nogoodfor P;

1. if() violates a nogood in U~ 1 Closure(a;,P), then B violates a nogood in Closure(a,P) .

Lemmas 3.8 and 3.9 indicate that symmetry breaking is tractable for ICSPs. Lemma 3.9 indicates that abstract no­ goods are needed only for frontier nodes of the search tree (i.e., closed nodes whose parents are open). Once its children are explored, the abstract nogood of the parent subsumes the abstract no goods of its children. Hence, maintaining the no­ good takes space O(IFI!VI) ifF is the set of frontier nodes. We formalize this result using variable decomposition trees.

Definition 3.10. A variable decomposition tree for a CSP P = {V, D, C), where D = {d1 , ... , dm}, is a search tree where nodes represent partial assignments for P and nodes are decomposed as follows: given a node representing a par­ tial assignment a, where dom(a) = { v; 1 , ··· , Vik }, its chil­ dren represent the partial assignments a; = a 1\ v;~<+ 1 = d; (1 ::; i ::; m) for some variable v;k+l E V \ dom(a).

Note that variable decomposition trees capture both static and dynamic variable orderings.

Theorem 3.11. Let P be an ICSP and let F be the set of frontier nodes in a variable decomposition search tree for P. Symmetry breaking for P requires 0 (IF IIV I) space for stor­ ing the nogoods. In addition, testing if a partial assignment B violates a nogood takes O(IFI!VI 2 ) time in the worst case.

The result above can be strengthened considerably in fact. We will show that search procedures exploring a variable de­ composition tree can remove all symmetries in constant time and space. Before presenting the theoretical results, we illus­ trate the intuition using depth-first search. The basic intuition comes from the structure of the abstract no goods. Consider the partial assignment

and assume that depth-first search tries to assign variable v6 and that the set of possible values is 1...10. The failure of v6 = 1 produces an abstract no good B which holds if

Since v1 , ..· , v5 remain instantiated when the next value is tried for V6, the abstract nogood for this part of this next branch holds if B(v6) = 1 imposing that V6 be assigned a value different from 1. The assignments v6 = 2 and v6 = 3 produce similar abstract nogoods. Now observe what hap­ pens for an assignment of a value i E 4 .. 10, say 6. The ab­ stract no good B is now defined as

which can be partially evaluated to alldifj{1, 2, 3, B(v6)). The disjunction of all these no goods can be partially evaluated to

bool ILABEL (P) { return ILABELA (P, E) ; } bool ILABELA ( (V, D, C), B) { } if dom(B) = V then return C(B); select v in V \ dom(B); A : = image( B); if image(B) =j:. D then select f in D \image( B); A . - AU{!}; forall (dE A) B' : = B 1\ v = d; if -.Failure ( (V, D, C), B') then if I LABELA ( (V, D, C), B' ) then return true ; return false;

which cannot be satisfied by any assignment to v6 . It fol­ lows that v6 must only be assigned to the previously assigned values 1, 2, 3 or to exactly one new value in 4 .. 10. In other words, in a variable decomposition tree, only some of the children need to be explored: those which assign variable Vik+t to a value in dom(o:) and exactly one other child. Note that this result is independent from the set of constraints. It is the essence of the labeling procedure for graph-coloring in [Kubale and Jackowski, 1985] and in the scene allocation problem in [Van Hentenryck, 2002]. This procedure, which breaks all symmetries for ICSPs, is formalized in Figure 1. It uses the function Failure(P, B) (P = (V, D, C)) which satisfies the property

To our knowledge, this paper provides the first formal proof that these algorithms break all the symmetries in their respec­ tive problems. To prove the correctness of ILABEL, and other related search procedures, it is useful to introduce the concept of compact variable decomposition tree.

Definition 3.12. A compact variable decomposition tree for an ICSP P = (V,D,C), where D = {d1, ... ,dm}, is a search tree where nodes represent partial assignments for P and nodes are decomposed as follows: given a node representing a partial assignment o:, where dom(o:) = { Viu ... , Vik }, for some variable Vik+t E V \ dom(o:), there are children representing the partial assignments o:i = o: 1\ Vik+l =do for all d0 E image( a) and exactly one child representing a partial assignment O:i = o: 1\ Vik+t = dn for some dn E D \image( a), if D \image( a) is not empty.

The following lemma, which states that compact variable de­ composition trees are complete, follows directly from the ex­ amination of the no goods above.

Lemma 3.13. Let P = (V, D, C) be an ICSP and S be all the complete assignments in a variable decomposition tree for P . Then, the closure {b o o: J o: E S 1\ b : D --+ Dis a bijection} is equal to Sol(P).

Our next lemma states that a compact variable decomposition tree never matches any no good generated during search.

Lemma 3.14. Let P be an ICSP and T be a compact vari­ able decomposition tree for P. The partial assignment o: of a node in T never matches any no good generated during the exploration ofT (except the one it possibly generates).

Proof By Lemma 3.9, it suffices to show that a partial assign­ ment B never matches a nogood generated by its siblings or the siblings of one of its ancestors in the tree. The proof is by induction on the depth of the tree. At the depth of B, the result follows from the inspections of the no good as discussed ear­ lier. Consider a depth dp' < dp and a nogood o: generated by one of the left or right branches at that depth. We can restrict attention to the projection of B to the variables instantiated at that depth, i.e., we can restrict attention to B' : dom(o:) --+ D satisfying 'tv E dom(o:): B'(v) = B(v).

We show that B' f/: Closure( o:, P). Let v be the variable assigned at depth d'. Observe that there exists a partial assign­ ment o:' such that o: = o:' 1\ v = e1 and B' = o:' 1\ v = e2, for some e1 , e2 E D and e1 =j:. e2 . By definition of a compact variable decomposition tree, the values e1 and e2 must belong to image(o:') U {d}, where d f/: image(o:').

Consider the case where e1 , e2 E image( a). That means that there exist Vi and v1 in dom( o:) such that o:( v) = o:(vi) =j:. o:(vj) and B'(v) = B'(vj) =j:. B'(vi). If B' E Closure( a, P), it can be rewritten as B' = boo: for some bijection b. Hence B' ( v) = B' (vi), which is impossible.

Assume now that e1 E image(o:') and e2 = d. It fol­ lows that o:(v) = o:(vi) for some Vi E dom(o:') and that B'- 1 (d) = {v}. IfB' E Closure(o:, P), then B' =boo: for some bijection. Hence B' ( v) = B' (vi) which is impossible.

Assume that e2 E image(o:') and e1 = d. Then, o:- 1 (d) = {v} and B'(v) = B'(vi) for some Vi E dom(o:'). If B' E Closure( o:, P), then B' = boo: for some bijection b. Hence, B' (v) = b(d)AB'- 1 (b(d)) = { v }, which is impossible since B'(v) = B'(vi) for some ViE dom(o:'). D

The correctness of Procedure ILABEL follows from the two lemmas above. Other search strategies, e.g., LDS, also re­ move all symmetries in constant time and space.

Theorem 3.15. Procedure ILABEL breaks all the symme­ tries in constant time and constant space for an ICSP P , i.e., it never matches any member of the closure of any nogood generated during search.

4 Piecewise-Interchangeable CSPs

In many applications, e.g., in resource allocation and schedul­ ing, the values are taken from disjoint sets but they are in­ terchangeable in each set. For instance, in the scene alloca­ tion problem, we can easily imagine a version of the problem where days are divided in morning and afternoon sessions. Actors probably have strong preferences (and thus different fees for the morning and afternoon sessions) but the day of the session may not matter. This paper captures this (more lim­ ited) form of interchangeability by piecewise interchangeable CSPs. We first define this class ofCSPs formally and then de­ rive similar results as for ICSPs. We state the main definitions and theorems only, since the derivation is similar to the one for ICSPs. As traditional, we use D1 + D2 to denote the dis­ joint union of D1 and D2. Our definitions and results only consider two distinct sets of values, for simplicity. It is easy to generalize them to an arbitrary number of sets.

Definition 4.1. Let Dt and D2 be two disjoint sets. A piece­ wise bijection b : Dt + D2 -+ Dt + D2 is a bijection defined as b(d) = b;(d) if dE D; where b; : D; -+ D; is a bijection (1 ::; i ::; 2) 0

Definition 4.2. Let P = (V, Dt + D2, C) be a CSP. P is piecewise value-interchangeable if, for each solution a E Sol(P) and each piecewise bijection b : Dt + D2 -+ Dt + D2, the function boa E Sol(P).

In the following, we use PICSP as an abbreviation for piece­ wise value-interchangeable CSP.

Definition 4.3. Let P = (V, Dt + D2, C) be a PICSP and a be a no good for P . The closure of o: for P, denoted by Closure( a:, P), is the set {boo: I b : Dt + D2 -+ Dt + D2 is a piecewise bijection} .

We now specify the abstract nogoods for PICSPs. The key intuition is to separate the values from Dt and D2 .

Definition 4.4. Let P (V, Dt + D2, C) be a PICSP and o: be a nogood for P. Let image(o:) = {dL . . . , dl, d'f , .. . , df}, where d} EDt , d'f E D2, and let

The abstraCt nogood of o: wrtP, denoted by Anogood(o:, P),

is the set offunctions"' : dom(o:) -+ Dt + D2 satisfying ViE l..k: allequal(vi E o:-t(d})) "f(Vj) 1\ Vi E l..k : Vvj E o:-t (d}) : Vj E Dt 1\ alldiff ("!( Vrt, .. . , "!( Vrt)) 1\ 1 k ViE l..l: allequal(vi E o:-t(d;)) "f(vi) 1\ ViE 1..1: Vvi E o:-t(d'f): Vj E D2 1\ alldiff ("!( Vr2, ... , "!( Vr2)). 1 I

Figure 2 depicts a labeling procedure PILABEL for PICSPs, which breaks all value symmetries in constant time and space. Procedure PI LABEL generalizes I LABEL by considering the already assigned values in both sets Dt and D2, as well as one new value (if any) from both sets.

Theorem 4.5. Procedure PILABEL breaks all the symme­ tries in constant time and constant space for PICSPs.

5 Wreath-Value Interchangeable CSPs

We now consider another, more complex, class of CSPs, which assigns a pair of values ( dt, d2) from a set Dt x D2 to each variable v. Values in Dt are fully interchangeable and, for a fixed value in Dt, the values in D2 are fully inter­ changeable as well. These problems are called wreath value­ interchangeable in this paper, because the symmetry group corresponds to a wreath product of symmetry groups [earner­ son, 1999]. Such problems arise naturally in a variety of ap­ plications in resource allocation and scheduling. Consider, for instance, the problem of scheduling a meeting where dif­ ferent groups must meet some day of the week in some room subject to constraints. The days are fully interchangeable and, on a given day, the rooms are fully interchangeable. Sym­ metry breaking for a wreath value-interchangeable CSP is tractable.

bool PILABEL(P) {return PILABELA(P,E); } bool PILABELA((V,Dt+D2,C),Bl { } if dom(B) = V then return C(B); select v in V \ dom(B); At : = image( B) n Dt; A2 : = image( B) n D2; if image( B) n Dt =/:- Dt then select f in Dt \image( B); At . - At U {!}; if image( B) n D2 =/:- D2 then select f in D2 \image( B); A2 . - A2 U {!}; forall (dE At U A2) (}' : = (} 1\ v = d; if -,Failure( (V, Dt + D2, C),(}') then if PILABELA({V,Dt +D2,C),(}') then return true ; return false;

Definition 5.1. Let Dt and D2 be two sets. A wreath bijec­ tion b : Dt x D2 -+ Dt x D2 is a bijection defined as

where bt : D1 -+ Dt is a bijection and b~ 1 (d1 E Dl) is a bijection D2 -+ D2.

Definition 5.2. Let P = (V, Dt x D2, C) be a CSP. P is wreath value-interchangeable if, for each solution a E Sol(P) and each wreath bijection b: D1 x D2 -+ Dt x D2, the function boa E Sol(P).

In the following, we use WICSP as an abbreviation for wreath value-interchangeable CSP. We also use the following nota­ tions. If d = ( dt, d2) is a pair, d[1] = dt and d[2] = d2. If T is a set of tuples, T[i] denotes the set { d[i] I d E T} and filter(T, i, d;) denotes the set { d I dE T 1\ d[i] = d;}. If o:: Dt x D2-+ D1 x D2 is an assignment, o:- 1 ((d1,D2)) denotes the set { o:-t ( (dt, d2)) I d2 E D2 }.

Definition 5.3. Let P = (V, Dt x D2, C) be a WICSP and o: be a no good for P. The closure of o: for P, denoted by Closure( a:, P), is the set {boo: I b : D1 x D2 -+ Dt x D2 is a wreath bijection}.

We now specify abstract nogoods for WICSPs.

Definition 5.4. Let P = (V, D1 x D2, C) be a WICSP and o: be a no good for P. Let image( o: )[1] = { dt, .. . , dk}, let filter(image(o:), 1, d;) = { dL .. . , dt.}, and let

The abstract no good of o: wrt P, denoted by Anogood( o:, P), is the set of functions"' : dom( o:) -+ D1 x D2 satisfying

[

[

bool WILABEL(P) {return WILABELA(P,f);} bool WILABELA((V,D1 x D2 ,C),B) { } if dom(B) = V then return C(B); select v in V \ dom(B); A1 : = image(B)[l]; if A1 f- D1 then select f in D1 \ A1 ; A1 : = A1 U {!}; forall (d1 E Ad A2 := filter(image(a),l,dl)[2]; if A2 f- D2 then select f in D2 \ A2 ; A2 . - A2 U {!} ; forall ( d2 E A2 ) B' := B 1\ v = (d1,d2); if ·Failure((V,D1 x D2 ,C),B') then if WILABELA((V,D1 x D2 ,C),B') then return true; return false;

Theorem 5.5. Procedure WILABEL breaks all the symme­ tries in constant time and constant space for a WICSP

6 Experimental Results

This section gives some preliminary results showing the ben­ efits of symmetry breaking on these classes of problems. Ta­ ble I gives results on graph coloring, an ICSP, and on parti­ tioned graph coloring, a PICSP. In partitioned graph coloring, the colors are divided in 4 groups and are fully interchange­ able in each group. The constraints express the usual graph­ coloring property: no two adjacent vertices are colored with the same color. Table I gives the result of coloring graphs with 50% edge density with at most n/(2 * log_2(n)) colors, where n is the number of nodes. The first column gives the number of nodes, the second column gives the time to color the graphs using the default labeling procedure, and the third and fourth columns report the time to color the graphs and the partitioned graphs with symmetry breaking. Note that the default labeling does not exploit symmetries and hence its time is similar for both graph coloring and partitioned graph coloring (second column). The last column gives the ratio of PILABEL and the default labeling procedure (the gains are too large for coloring to be reported as a ratio). All re­ sults are an average of 5 runs in milliseconds under SICStus­ Prolog. They clearly show that symmetry breaking on these CSPs brings significant benefits.

7 Conclusion

This paper studied three classes of CSPs for which symme­ try breaking is tractable. These CSP classes feature vari­ ous forms of value interchangeability and allow symmetry breaking to be performed in constant time and space during search. Experimental results also show the benefits of sym­ metry breaking on these CSPs, which encompass many prac­ tical applications. There are many directions for future re­ search. Of particular interest is the study of tractable classes ofCSPs exhibiting variable symmetries where the set V has a complex structure (e.g., a Cartesian product). There are sev­ eral classes of such CSPs for which symmetry breaking is tractable, although more complex. Finding effective search procedures for these CSPs is also a challenging problem.

8 Acknowldegments

Special thanks to the reviewers for their very interesting com­ ments. All authors are partly supported by a STINT insti­ tutional grant IG2001-67 of STINT. P. Van Hentenryck is partly supported by an NSF ITR Award DMI-0121495. The Sweden-based authors are also supported by grant 221-99369 of the Swedish Research Council.