Solving Strategies for Highly Symmetric CSPs

1 Introduction

Symmetry is present in many natural and artificial set­ tings. A symmetry is a transformation of an entity such that the transformed entity is equivalent to and indis­ tinguishable from the original one. We can see symme­ tries in nature (a specular reflection of a daisy flower) , in human artifacts (a central rotation of 180 degrees of a chessboard) , and in mathematical theories (inertial changes in classical mechanics). The existence of sym­ metries in these systems allows us to generalize the prop­ erties detected in one state to all its symmetric states.

Regarding constraint satisfaction problems (CSPs), many real problems exhibit some kind of symmetry, em­ bedded in the structure of variables, domains and con­ straints. During search, if two or more states of a prob­ lem are related by a symmetry, it means that all of them represent the same state, so it is enough to visit only one of them. This causes a drastic decrease in the size of the search space, which has a very positive impact on the efficiency of the constraint solver.

In this paper, we propose two strategies for symmetry exploitation, which can speed-up significantly the solv­ ing process of CSPs with many symmetries. We have Carme Torras Inst. Robotica i Informatica Industrial CSIC-UPC Gran Capita 2-4, 08034 Barcelona Spain used these strategies to solve the problem of generating balanced incomplete block designs (BIBD from now on), a combinatorial problem of interest in statistics, coding theory and computer science. With them, we are able to solve the BIBD generation problem with a simple algo­ rithm (FC-CBJ) for a wide set of designs.

*This research is supported by the Spanish CICYT proyect TIC96-0721-C02.

This paper is organized as follows. In Section 2, we introduce some basic concepts. In Section 3, we explain two strategies for symmetry exploitation during search. In Section 4, we present the problem ofBIBD generation. In Section 5, we formulate .the BIBD generation as a CSP and give empirical results. In Section 6, we revise previous approaches to this topic. Section 7 contains conclusions and future work.

2 Basic Definitions

Constraint satisfaction. A finite CSP is defined by a triple (X,'D,C), where X = {x1, ... ,xn} is a set of n variables, 'D = {D(x1), ... , D(xn)} is a collec­ tion of current domains where D(x;) is the finite set of possible values for variable x; , and C is a set of con­ straints among variables. A constraint c; on the or­ dered set of variables var( c;) = (x;,, .. . , x;"<'>) spec­ ifies the relation rel ( ci) of the allowed combinations of values for the variables in var( c;). An element of rel(c;) is a tuple (v;,, ... , v;r(o), v; E Do(xi), where Do ( x;) represents the initial domain of x; . An element of D(x;,) x · · · x D(x;r(i)) is called a valid tuple on var(c;) . A solution of the CSP is an assignment of values to vari­ ables which satisfies every constraint. A value a is good for a variable x; if a solution includes the assignment ( x;, a). Typically, CSPs are solved by depth-first search algorithms with backtracking. At a point in search, P is the set of assigned or past variables, and F is the set of unassigned or future variables. The variable to be assigned next is called the current variable.

Symmetries. A symmetry on a CSP is a collection of bijective mappings { (), 01, ... , On},

that preserve the set of constraints, i.e., Vcj E C with var(cj) (xit>"''Xj,Ul) and rel(cj) {(vit> ... , Vj·(i))}, the transformed constraint cJ with var(cJ) (11(xit), ... , 11(xir(i))) and rel(cJ) {(11j.(Vj.), .. . ,11jr(j)(vj,(i)))}, is in C. 1

An example of a symmetry on the 4-queens problem appears in Figure 1. Domains are Do(xl) = {1, 2, 3, 4}, Do(x2) = {5, 6, 7, 8}, Do(xa) = {9, 10, 11, 12}, Do(x4 ) = {13, 14, 15, 16}. A central ro­ tation of 180 degrees exchanges variables x 1 with x4 and x2 with xa, and value domains are mapped as indicated. This transformation is a symmetry because all the map­ pings (on variables and domains) are bijective, and the set of constraints is left invariant by the transformation of variables and values. For example, the transformed constraint cf2 is computed as follows,

Thus, cf2 = ca4. Some symmetries leave subsets of vari­ ables unchanged. They are of special interest, as we will see in the next paragraph.

Symmetries and depth-first search. A search state s is characterized by an assignment of past variables, plus the current domains of future variables. It defines a subproblem of the original problem, where the domain of each past variable is reduced to its assigned value and the relation rel ( c;) of each constraint c; is reduced to its valid tuples with respect to current domains. A symmetry holds at state s if it is a symmetry of the subproblem occurring at s. A symmetry holding at s is said to be local to s if it does not change neither past variables nor their assigned values. A symmetry local to the initial state is a global symmetry of the problem.

The notion of local symmetry is important because of the use of symmetries during search. If a state reports failure, all the states symmetric to it can be removed.

1 Through an abuse of notation, we denote a symmetry {8,8t, ... ,8n} by its variable mapping e.

Since constraint satisfaction algorithms are based on depth-first search with backtracking, they may only re­ move states that are in the subtree below the current node, but never above it . Therefore, we are only inter­ ested in symmetries connecting states below the current node, that is, leaving the set of past variables unchanged. These symmetries are local to the current node. In the rest of the paper, we will consider local symmetries only.

3 Solving Strategies

In the following subsections, we describe two practical strategies for highly symmetrical CSPs, which can be embedded in any constraint satisfaction algorithm. Both are based on the detection of local symmetries at each search state. Automatic discovery of symmetries is a too complex task to be carried out at run time. Instead, we take a simpler approach. From an initial analysis of the considered problem, we identify a set of symmetries which may appear along the search. When a new state is generated, we check which of these previously identified symmetries are local to this state.

3.1 Breaking Symmetries While Searching

Let s be a search state where the symmetry 11 local to s involves a future variable x; in the following form,

If Xi is assigned in the next step, symmetry 11 no longer holds in the current subproblem after Xi assignment. To see this, it is enough to realize that x; is now a past vari­ able (which cannot be changed) and 11 will change it . In this case, we say that the assignment of Xi breaks symme­ try 11. If at state s several symmetries 11, ¢, 1/J, ... are local to s, all involving variable x;, assigning x; will break all these symmetries: no state in the current subproblem will be "repeated" by the action of these symmetries. This positive effect is only due to the assignment of x;, taken as the current variable. This is the rationale for our variable selection heuristic.

Symmetry-breaking heuristic: Select for assign­ ment the variable involved in the greatest number of symmetries local to the current state.

This greedy heuristic tries to break as many symme­ tries as possible in the next assignment. When it is ap­ plied consistently throughout the search tree, its positive effects accumulate. If x1 is the variable selected at the first tree level, no matter which value is assigned to it, all symmetries involving x1 are broken below level 1. If x2 is the variable selected at the second tree level, no matter which value is assigned to it , all symmetries in­ volving x1 and x2 are broken below level 2, and so on. 2 This heuristic tries to maximize the total number of bro­ ken symmetries at each level of the search tree. It causes the following benefits.

2 It could be argued that the assignment of x2 may restore a symmetry 8 broken by the assignment of X!, if 8 exchanges both variables and their values. But now 8 is no longer a local symmetry, given that it acts on past variables.

1. Lookahead of better quality. A lookahead algo­ rithm prunes future domains taking into account past assignments. When symmetries on future vari­ ables are present, some of the lookahead effort is unproductive. If there is a symmetry () such that B(xj) = Xk, with Xj,Xk E F, after lookahead on D(xj), lookahead on D(xk) is obviously redundant because it will produce results equivalent (through B) to lookahead on D(xj)· If no symmetries are present, no lookahead effort will be unproductive. Therefore, the more symmetries are broken, the less unproductive effort lookahead performs. When the number of symmetries is high, savings in unproduc­ tive lookahead effort could be substantial.
2. Better value selection. Let us suppose a problem with solution. At state s, there is a symmetry B(xj) = Xk, with Xj,Xk E F. Let sol(xj) = a and sol(xk) = b be the solution values for these two variables. Because of the symmetry, there is another solution with sol(xj) = b and sol(xk) = a. Therefore, if x j is selected as current variable, both values a, bare good to bring search to a solution. In a more general setting, this argument supports the fact that a variable involved in many symmetries will have many good values in its domain.

Some of these facts are illustrated in the following ex­ ample. Let us consider the equation, xy - z = 4, where all variables take values in {1, 2, 3}. There is a symme­ try, B(x) = y, and two solutions (x = 2, y = 3, z = 2) and (x = 3, y = 2, z = 2). Figure 2 displays two search trees for this equation, one following the variable order­ ing z, x, y and the other x, y, z. In the first tree, symme­ try () is not broken after assigning z, so symmetric states appear inside subtrees at the first level. In the second tree, symmetry () is broken after assigning x, and sym­ metric states only appear between subtrees at the first level but not inside them. In addition, D0 (x) has two good values (2 and 3), but D0 (z) has only one (2).

3.2 Value Removal After Failure

Lets be a search state, where x; is selected as the current variable and value a is tried without success. At this point, a backtracking-based algorithm will try another value for x;. If() is a symmetry local to s, we can remove B;(a) (the value symmetric to a) from D(B(xi)), because it cannot belong to any solution including the current assignment of past variables. If all values of x; are tried without success and the algorithm backtracks, all values removed in this way should be restored. If x; is involved in several symmetries, this argument holds for each of them separately.

This method of value removal after failure provides further support to the symmetry-breaking heuristic of Section 3.1. The more local symmetries a variable is involved in, the more opportunities it offers for symmet­ ric value removal in other domains if a failure occurs. This extra pruning is more effective if it is done at early levels of the search tree, since each pruned value repre­ sents removing a subtree on the level corresponding to the variable symmetric to the current one.

An example of this value removal arises in the pigeon­ hole problem: locating n pigeons in n - 1 holes such that each pigeon is in a different hole. This problem is formulated as a CSP by associating a variable x; to each pigeon, all sharing the domain { 1, ... , n - 1}, under the constraints x; :j:. Xj, 1 ~ i,j ~ n, i :j:. j. Among others, this problem has a collection of symmetries in domains,

(I is the identity mapping). If search is performed by forward checking and variables and values are as­ signed lexicographically, the first dead-end occurs when (xt,1),(x2,2), ... ,(xn-l,n- 1), causing D(xn) to be empty. D(xn-d has no more values, so backtracking goes back to Xn-2· There, it finds that the only remain­ ing value, n - 1, is symmetric to n - 2 which failed, so n - 1 can be pruned and no more values remain in D(xn-2)· Backtracking goes back to Xn-J where, by the same argument, the two remaining values are pruned. This process goes on up to reach x1 , where all its re­ maining values are pruned and search terminates with failure. Only the leftmost branch of the search tree ts generated, and the rest of the tree i~ pruned.

4 BIBDs

Block designs are combinatorial objects satisfying a set of integer constraints [Hall, 1986; Colbourn and Dinitz, 1996]. Introduced in the thirties by statisticians working on experiment planning, nowadays they are used in many other fields, such as coding theory, network reliability, and cryptography. The most widely used designs are the Balanced Incomplete Block Designs (BIBDs).

Formally, a (v,b,r,k,>.)-BIBD is a family of b sets (called blocks) of size k, whose elements are from a set of cardinality v, k < v, such that every element belongs exactly to r blocks and every pair of elements occurs exactly in >. blocks. v, b, r , k, and >. are called the pa­ rameters of the design. Computationally, designs can be represented by a v x b binary matrix, with exactly r ones per row, k ones per column, and the scalar product of every pair of rows is equal to >. . An example of BIBD appears in Figure 3.

There are three well-known necessary conditions for the existence of a BIBD:

1. rv = bk,
2. >.(v- 1) = r(k- 1), and
3. b ~ v (Fisher's inequality) .

However, these are not sufficient conditions. The sit­ uation is summarized in [Mathon and Rosa, 1990], that lists all parameter sets obeying these conditions , with r :::; 41 and 3 :::; k :::; v/2 (cases with k :::; 2 are triv­ ial , while cases with k > v/2 are represented by their corresponding complementaries, which are also block de­ signs). For some parameter sets satisfying the above con­ ditions, it has been established that the corresponding design does not exist; for others, the currently known bound on the number of non-isomorphic solutions is provided; and finally, some listed cases remain unset­ tled . The smallest such case is that with parameters (22,33,12,8,4}, to whose solution many efforts have been devoted [Wallis, 1996, Chapter 11].

Some (infinite} families of block designs (designs whose parameters satisfy particular properties) can be constructed analytically, by direct or recursive meth­ ods [Hall, 1986, Chapter 15], and the state of the art in computational methods for design generation is de­ scribed in [Colbourn and Dinitz, 1996; Wallis, 1996] . The aforementioned unsettled case, with vb = 726 bi­ nary entries, shows that exhaustive search is still in­ tractable for designs of this size. In the general case, the algorithmic generation of block designs is an NP prob­ lem [Corneil and Mathon, 1978] .

Computational methods for BIBD generation, either based on systematic or randomized search procedures, suffer from combinatorial explosion which is partially due to the large number of isomorphic configurations present in the search space. The use of group actions goes precisely in the direction of reducing this isomor­ phism. Although up to our knowledge, BIBD generation has not been tackled from the CSP viewpoint , it appears to be a wonderful instance of highly symmetric CSP, thus offering the possibility to assess the benefits of different search strategies on such problems.

5 Experimental Results

The problem of generating a (v, b, r , k, >.) -BIBD can be formulated as a CSP as follows. Two rows i and j of the BIBD should have exactly >. ones in the same columns. We represent this by >. variables Xijp, 1 :::; p :::; A, where Xijp contains the column of the pth one common to rows i and j. There are v(v- 1}/2 row pairs, so there are >.v( v - 1} /2 variables , all sharing the domain { 1, ... , b} . From these variables , the BIBD table T , a v x b binary matrix, is computed as follows,

Constraints are expressed in the following terms,

where 1:::; p ,p':::; .X , 1:::; i , j :::; v , 1 :::; c:::; b. This problem presents many local symmetries. We consider the following ones relating future variables,

1. Variable mapping exchanges Xij p and Xijp', domain mappings are the identity; this symmetry occurs among variables of the same row pair .
2. Variable mapping is the identity, one domain map­ ping exchanges values c1 and c2 ; this symmetry oc­ curs when T[l , c1] = T[l , c2] for l = 1, ... , v.
3. Variable mapping exchanges Xijp and Xi'j'p', do­ main mappings are the identity; this symmetry oc­ curs when T[i , c] = T[i' , c] and T[j , c] = T[j' 1 c] for c = 1, ... , b.
4. Variable mapping exchanges X;j,p and Xi)2p', the domain mappings corresponding to these variables exchange values c1 and c2 ; this symmetry occurs when,

1. Variable mapping exchanges X;,j ,p and X; 2 )2p', the domain mappings corresponding to these variables exchange values c1 and c2 ; this symmetry occurs when,

These symmetries have a clear graphical interpretation. Symmetry (1} is inherent to the formulation. Symme­ try (2) relates values of the same variable corresponding to equal columns. Symmetry (3} relates variables corre­ sponding to equal rows. Symmetry ( 4} relates variables sharing row i , and rows j1 and h that are equal but for two columns c1 and c2 . These columns are also equal but for rows it and h . Exchanging rows it and h, and columns c1 and c2 , matrix T remains invariant . Symme­ try (5) follows the same idea although it is more complex. It occurs when exchanging rows i1 and i2, rows it and h, and columns c1 and c2, matrix T remains invariant. It is worth noting that these symmetries keep invariant matrix T because they are local to the current state, that is, they do not change past variables.

Symmetries are detected dynamically at each visited node. The specific implementation of the symmetry­ breaking heuristic performs a weighted sum of the num­ ber of symmetries involving each future variable, where symmetries ( 4) and ( 5) are considered of less importance than the others.

BIBD generation is a non-binary CSP. We use a for­ ward checking alf$orithm with conflict-directed back­ jumping (Fc-CBJ lProsser, 1993]) adapted to deal with non-binary constraints, with Brelaz heuristic [Brelaz, 1979] for variable selection and random value selection, as reference algorithm. This algorithm is modified to in­ clude the symmetry-breaking heuristic for variable selec­ tion, with Brelaz as tie-breaker, producing Fc-CBJ-SB. Adding to this algorithm the strategy of value removal after failure, we obtain Fc-CBJ-SB-VR. We compare the performance of these algorithms generating all BIBDs with vb < 1400 and k = 3, all having solution. Since the performance of the proposed algorithms depends on random choices, we have repeated the generation of each BIBD 50 times, each with a different random seed. Ex­ ecution of a single instance was aborted if the algorithm visited more than 50,000 nodes .

Empirical results appear in Table 1, where for each al­ gorithm and BIBD, we give the number of solved prob­ lems within the node limit and the average CPU time in seconds for the 50 instances. Comparing Fc-CBJ and Fc-CBJ-SB-VR, we see that Fc -CBJ solves 899 in­ stances while Fc-CBJ-SB-VR solves 2382 out of the 2400 instances executed. Fc-CBJ does not solve any instance for 8 specific BIBDs, while Fc-CBJ-SB-VR provides so­ lution for all BIBDs tested. Regarding CPU tii:ne, Fc­ CBJ-SB-VR dominates FC-CBJ in 44 out of the 48 BIBDs considered, and this dominance is of one or two orders of magnitude in 39 cases . These results show clearly that the proposed strategies improve greatly the efficiency of the Fc-CBJ algorithm for BIBD generation.

Fc-CBJ-SB results show that this algorithm almost achieves Fc-CBJ-SB-VR performance. Fc-CBJ-SB solves 2362 instances, 20 less than Fc-CBJ-SB-VR, requiring slightly more time on the average. So, for BIBD gen­ eration, the symmetry-breaking heuristic is the main re­ sponsible for the savings in search effort , while value re­ moval plays a very secondary role.

We also reimplemented Fc-CBJ adding constraints X ijp < Xijp' if p < p', to break type (1) symmetries. The resulting algorithm, which included the extra pruning capacities caused by these new constraints, runned sig­ nificantly slower than the original Fc-CBJ in all BIBDs with .X> 1.

6 Related Work

Previous work on symmetries and CSPs can be classified in two general approaches. An approach, where our work fits in, consists in modifying the constraint solver to take advantadge of symmetries. A modified backtracking al­ gorithm appears in [Brown et al., 1988], testing each node to see whether it is the appropriate representative ofthose states symmetric to it. Considering specific sym­ metries, [Freuder, 1991] discusses the pruning of neigh­ borhood interchangeable values of a variable. Another strategy [Roy and Pachet , 1998] conSiders value pruning between permutable variables. Interestingly, these two strategies are particular cases of the more general strat­ egy presented in Section 3.2. It is easy to show that ,

1. Let x; E F, a, b E D(x; ). Values a, b are neighbor­ hood interchangeable iff there exists a symmetry e such that B(xi) = x;, B;(a) =b.
2. Let x;, x j E F . Variables x;, x j are permutable iff there exists a symmetry B such that B(x;) = Xj, B;(a) =a, a E D(x;).

So, if a is assigned to x; and fails, (1) all values neigh­ borhood interchangeable with a in D(x;), and (2) all values a appearing in future domains of variables per­ mutable with x;, can be removed. Although developed independently, our strategy of value removal after failure can be seen as a particular case of the symmetry exclu­ sion method introduced by [Backofen and Will, 1998] for concurrent constraint programming, and applied to the CSP context by [Gent and Smith, 1999].

Another approach consists in modifying the symmetric problem to obtain a new problem without symmetries, but keeping the non-symmetric solutions of the original one. To do this, new constraints are added to the origi­ nal problem in order to break the symmetries. Detecting symmetries and computing the new constraints is per­ formed by hand in [Puget, 1993]. Alternatively, existing symmetries and the corresponding symmetry-breaking predicates (in the context of propositional logic) are com­ puted automatically in [Crawford et al., 1996].

7 Conclusions

In this paper we have analysed how to take symmetry into account to reduce search effort. We have presented two strategies to exploit symmetries inside a depth-first search scheme. These strategies have been tested on a highly symmetric combinatorial problem, namely the generation ofBIBDs, an NP problem which has triggered a considerable amount of research on analytic and com­ putation<;tl procedures. Its wide variability in size and difficulty makes it a very appropriate benchmark for al­ gorithms aimed at exploiting symmetries in CSPs.

We believe that systematic procedures are more likely to shed light on the solution of difficult instances of the problem, whereas randomized algorithms may be quicker at finding solutions in easier cases. The present work has not been aimed at solving a particular such instance, but instead at proposing and evaluating tools to deal with symmetries. In this respect, the proposed strategies have been shown to be effective in reducing search effort.

It is worth mentioning that there is always a trade-off between the effort spent in looking for and exploiting symmetries, and the savings attained. Thus, instead of considering all possible symmetries, it is advisable to es­ tablish a hierarchy of them and try to detect the simplest first, as we have done.

Concerning future work, we plan to compare our strategies with the alternative approach of reformulating the original problem by adding new constraints to break problem symmetries. We also want to assess to what extent our approach depends on the type and number of symmetries occurring in a particular problem. We would like to identify criteria for value selection which complement our symmetry-breaking heuristic for vari­ able selection. Moreover, the experimentation should be extended to other BIBD families, and the benefits ob­ tained validated by applying these strategies to other domains.

Acknowledgements

We thank Ja.vier Larrosa and the anonymous reviewers for their constructive criticisms.