The Difference All-Difference Makes

1 Introduction

Many real-world problems involve all-different constraints. For example, every fixture for a sports team must be on a different date. Many of the constraint satisfaction toolkits theref?re provi~e specialized algorithms for efficiently rep­ resentmg and, m some case, reasoning about all-different constraints. Alternatively, we can expand all-different con­ straints into a quadratic number of binary not-equals con­ straints. However, it is Jess efficient to do this, and the transla­ ~ion loses some semantic information. The aim of this paper IS to ~how the benefits of keeping with a non-binary repre­ sentatiOn. We prove that we can achieve much higher levels of consistency in the non-binary representation compared to the binary. We show experimentally that these high levels of consistency can reduce search dramatically.

*The authors are members of the APES research group, http://www.cs.strath.ac.ukl apes. We thank our colleagues in the g~oup at the Universities of Strathclyde and Leeds, most espe­ Cially Paul Shaw. The second author is supported by EPSRC award GR/K/65706.

2 Formal background

A c?nstraint satisf~ction problem (CSP) is a triple (X , D, C) . X IS a set of variables. For each x; E X, D; is the do­ main of the variable. Each k-ary constraint c E C is defined over a set of variables ( x 1 , ... x k) by the subset of the carte­ sian product D1 x ... Dk which are consistent values. An all-different constraint over ( x 1, ... xk) disallows the values Dt X ·: ·D_k- {(a_l, .. . ak) I a; ED; &'rfu ::j:. v.au ::j:. av}· A solutiOn IS an assignment of values to variables that is con­ sistent with all constraints.

Many lesser levels of consistency have been defined for binary constraint satisfaction problems (see [Debruyne and ~es_siere, 1997] for references). A problem is ( i, j)-consistent tff It has non-empty domains and any consistent instantia­ tion of i variables can be extended to a consistent instan­ tiation involving j additional variables. A problem is arc­ consistent (A C) iff it is (I , I )-consistent. A problem is path­ consistent (PC) iff it is (2, I)-consistent. A problem is strong path~consist_ent iff it is (j, I)-consistent for j :::; 2. A prob­ lem IS path mverse consistent (PIC) iff it is (I , 2)-consistent. A problem is neighborhood inverse consistent (NIC) iff any value for a variable can be extended to a consistent instantia­ tion for its immediate neighborhood. A problem is restricted path-consistent (RPC) iff it is arc-consistent and if a variable assigned to a value is consistent with just a single value for an adjoining variable then for any other variable there exists a value compatible with these instantiations. A problem is sin­ gleton arc-consistent (SAC) iff it has non-empty domains and for any instantiation of a variable, the problem can be made arc-consistent.

Man~ of these definitions can be extended to non-binary constramts. For example, a (non-binary) CSP is generalized arc-consistent (GAC) iff for any variable in a constraint and value that it is assigned, there exist compatible values for all the other variables in the constraint [Mohr and Masini, 1988]. Regin gives an efficient algorithm for enforcing generalized arc-consistency on a set of all-different constraints [Regin, 1994]. We can also maintain a level of consistency at every node in a search tree. For example, the MAC algorithm for binary CsPs maintains arc-consistency at each node in the search tree [Gaschnig, 1979]. As a second example, on a non­ binary problem, we can maintain generalized arc-consistency (MGAC) at every node in the search tree.

Following [Debruyne and Bessiere, 1997], we call a consistency property A stronger than B (A 2: B) iff in any prob­ lem in which A holds then B holds, and strictly stronger (A > B) iff it is stronger and there is at least one problem in which B holds but A does not. We call a local consis­ tency property A incomparable with B (A ,....., B) iff A is not stronger than B nor vice versa. Finally, we call a local con­ sistency property A equivalent to B iff A implies B and vice versa. The following identities summarize results from [De­ bruyne and Bessiere, 1997] and elsewhere: strong PC> SAC > PIC > RPC > AC, NIC > PIC, NIC ,....., SAC, and NIC ,....., strong PC.

3 Generalized arc-consistency

All-different constraints are network decomposable [Dechter, 1990] (abbreviated to decomposable in this paper) as they can be represented by binary constraints on the same set of vari­ ables. In this section, we give some theoretical results which identify the level of consistency achieved by GAC on decom­ posable constraints like the all-different constraint.

In general, GAC on decomposable constraints may only achieve the same level of consistency as AC on the binary representation. The problem is that decomposable constraints can often be decomposed into smaller constraints. For ex­ ample, we can decompose an n-ary all-different constraint into n( n - 1) /2 binary all-different constraints, and enforc­ ing GAC on these only achieves the same level of consistency as AC on the binary representation. We can achieve higher levels of consistency if we prohibit too much decomposition of the non-binary constraints. For example, we can insist that the constraints are triangle preserving. That is, we insist that, if there is a triangle of variables in the constraint graph of the binary representation, then these variables must occur to­ gether in a non-binary constraint. Binary constraints can still occur in a triangle preserving set of constraints, but only if they do not form part of a larger triangle. Under such a re­ striction, GAC is strictly stronger than PIC, which itself is strictly stronger than AC.

Theorem 1 On a triangle preserving set of decomposable constraints GAC is strictly stronger than PIC on the binary representation.

Proof: Consider a triple of variables, x;, Xj, Xk and any value for x; from its generalized arc-consistent domain. The proof divides into four case. In the first, x; and x j appear in one constraint, and x; and Xk in another. As each of these constraints is arc-consistent, we can find a value for x j con­ sistent with x;, and for xk consistent with x;. As the (non­ binary) constraints are triangle preserving, there is no direct constraint between Xj and X k so the values for Xj and Xk are consistent with each other. Hence, the binary representation of the problem is PIC. The other three cases follow a similar argument. To show that GAC is strictly stronger, consider an all-different constraint on 4 variables each with domains of size 3. This problem is PIC but not GAC. o

A corollary of this result is that GAC on a triangle preserv­ ing set of decomposable constraints is strictly stronger than RPC or AC on the binary representation. We can also put an upper bound on the level of consistency that GAC achieves.

Theorem 2 NIC on the binary representation is strictly stronger than GAC on a set of decomposable constraints.

Proof: Consider any variable and value assignment. NIC ensures that we can assign consistent values to the vari­ able's neighbors. However, any (non-binary) constraint in­ cluding this variable has all its variables in the neighbor­ hood. Hence, the (non-binary) constraint is GAC. To prove strictness, consider a problem with five all-different con­ straints on {x1, x2, x3}, on {x1, x3 , x4}, on {x1, x4 , x5}, on {x1, xs, x6}, and on {x1, x 6 , x2}. in which x1 has the unitary domain {1} and every other variable has the domain {2 , 3}. This problem is GAC, but enforcing NIC. shows that it is in­ soluble. o

Finally, GAC on decomposable constraints, is incompara­ ble to strong PC and SAC, even when restricted to triangle preserving sets of constraints.

Theorem 3 On a triangle preserving set of decomposable constraints, GAC is incomparable to strong PC and to SAC.

Proof: Consider an all-different constraint on 4 variables, each with the same domain of size 3. The binary representa­ tion of the problem is strong PC and SAC, but enforcing GAC shows that it is insoluble.

Consider the problem in the proof of Theorem 2 with five all-different constraints. This problem is GAC, but enforcing strong PC or SAC shows that it is insoluble.

These results are summarized in Figure 1.

4 Quasigroup problems

Quasigroup problems lend themselves to a non-binary rep­ resentation using all-different constraints. A quasigroup is a Latin square, an by n multiplication table in which each entry appears once in every row and column. Quasigroups model a variety of practical problems like tournament scheduling and designing drug tests. Quasigroup completion, the problem of completing a partial filled quasigroup, has been proposed as a constraint satisfaction benchmark [Gomes and Selman, 19971

An order n quasigroup completion problem can be repre­ sented as a non-binary constraint satisfaction problem with n 2 variables, each with a domain of size n. The constraints are 2n all-different constraints of size n, one for each row and column, and any number of unitary constraints or preassign­ ments. The special structure of these constraints allows us to prove some tighter results.

Theorem 4 In quasigroup completion problems, GAC is equivalent to NIC.

Proof: We need to show that GAC implies NIC. The neigh­ borhood of any variable in an order n quasigroup comple­ tion problem are the 2n - 1 variables that appear in the 2 all-different constraints that contain the variable. As these constraints are GAC, we can find consistent instantiations for each of the variables. In the binary representation, none of these variables have a direct constraint with each other. Hence, this is a consistent instantiation for the neighborhood. 0

GAC on quasigroup problems remains strictly stronger than PIC and incomparable to strong PC and to SAC.

Theorem 5 In quasigroup completion problems, GAC is strictly stronger than PIC.

Proof: By theorem 1, GAC is stronger than PIC. To show that it is strictly stronger, consider an order 4 quasigroup, in which 3 diagonal elements have domains {1}, and all the other el­ ements (including the other diagonal element) have domains {2, 3, 4 }. This problem is PIC but is not GAC. o

Theorem 6 In quasigroup completion problems, GAC is in­ comparable to strong PC and to SAC.

Proof: Consider the problem from the last proof. This prob­ lem is strong PC and SAC but is not GAC.

Consider an order 3 quasigroup. Let every element have a domain {1 , 2, 3} except the top right which has the domain { 1, 2}, the bottom left which has the domain { 1, 3} and the bottom right which has the domain {2, 3} . This problem is GAC but enforcing strong PC or SAC shows that it is insolu­ ble. o

What can we learn from these results? First, on quasi­ group completion problems, we achieve the maximum level of consistency (viz. NIC) possible for a GAC procedure on decomposable constraints. And second, we achieve this at very moderate cost. Regin's algorithm for achieving GAC on a set of all-different constraints has a cost that is polynomial in n. By comparison, enforcing NIC on binary constraints is exponential in the size of the neighborhood (which is 0( n) in this case).

5 Maintaining GAC and AC

We now compare an algorithm that maintains GAC on de­ composable constraints over one that maintains AC on the binary representation. We say that algorithm A dominates algorithm B if when A visits a node then B also visits the equivalent node in its search tree, and strictly dominates if it dominates and there is one problem on which it visits strictly fewer nodes. Using the previous results, we can reduce our analysis to comparing algorithms that maintain NIC, PIC and AC. In fact, we do better than this and prove some general re­ sults about algorithms that maintain any level of consistency stronger than FC in which we just filter domains. This cov­ ers algorithms that maintain NIC, PIC and AC, as well those that maintain RPC and SAC. We shall use A-consistent and B-consistent to denote any two such levels of consistency.

We assume throughout a static variable and value ordering. We can then associate each node in the search tree with the sequence of value assignments made. We say that a node (a1 , . . . , a;) is A-compatible with another node (a1 , ... , aj ) where j < i, if enforcing A-consistency at ( a 1 , ... , aj) does not remove a; from the domain of the respective variable. First, we give a necessary and sufficient condition for a node to be visited.

Theorem 7 A node is visited by an algorithm that maintains A-consistency iff it is consistent, it is A-compatible with all its ancestors, and its parent can be made A -consistent.

Proof: (=>) The proofs of the first and third conjuncts are similar to those in [Kondrak and van Beek, 19971. For the second, suppose that node (a1 , ... , a;) is not A-compatible with one of its ancestors and it is visited. Let ( a 1 , ... , aj ), with j < i, be the shallowest of those ancestors. Since ( a 1 , ... , aj) is an ancestor of ( a 1 , . .. , a;), it is also vis­ ited. When we visit node (a1 , ... , aj) and A-consistency is enforced, a; is pruned out from the domain of x;. Node (a 1 , .. . , a;_!) cannot therefore be extended to (a 1 , ... , a;). This is a contradiction.

(¢::) WLOG assume that node (a1 , .. . ,a;_1) is the shallowest node that can be made A-consistent, its child (a1 , ... , a;) is consistent and A-compatible with all its an­ cestors, but the child is not visited. Since ( a1 , ... , a;) is con­ sistent and A-compatible with all its ancestors, a; is in the domain of x;. At node (a1 , .. . , a;_ 1), we do not annihilate any of the domains of future variables because the node can be made A-consistent. The branch will therefore be extended to the remaining values of the next variable x;. One of these values is a; and therefore node (a1 , ... , a;) is visited. o

This results lets us rank algorithms in the hierarchy pre­ sented in [Kondrak and van Beek, 19971.

Theorem 8 If A-consistency is (strictly) stronger than B­ consistency then maintaining A -consistency (strictly) domi­ nates maintaining B-consistency.

Proof: All nodes visited by an algorithm that maintains A-consistency, are A-consistent with all their ancestors and have parents that can be made A-consistent. But as A­ consistency is stronger than B-consistency, all these nodes are B-consistent with all their ancestors and have parents that can be made B-consistent. Hence maintaining A-consistency dominates maintaining B-consistency. To show strictness, consider any problem that is B-consistent but is not A­ consistent. 0

From this result, it follows that MGAC on decomposable constraints strictly dominates MAC on the binary representa­ tion, and that MAC itself strictly dominates FC. We can also prove the correctness of MGAC and MAC using the follow­ ing general result.

Theorem 9 Maintaining A-consistency is correct.

Proof: Soundness is trivial as only consistent nodes are visited. For completeness, suppose that some n-level node is consistent. Since this node is consistent, all its ances­ tors are also consistent. WLOG consider the deepest node k = (a1 , . . . , a;) , i ~ 1 that is not visited, and its parent is visited. When node (a1 , .. . , a;_!) is visited A-consistency is enforced, and since all its descendants are consistent, there is no domain wipe-out. Therefore, k is visited. o

6 Experimental results

To demonstrate the practical relevance of these theoretical re­ sults, we ran experiments in three domains.

6.1 Quasigroup completion

Gomes and Selman have proposed random quasigroup com­ pletion problems as a benchmark that combines some of the best features of random and structured problems [Gomes and Selman, 1997]. For these problems, there is a phase transi­ tion from a region where almost all problems are soluble to a region where almost all problems are insoluble as we vary the percentage of variables preassigned. The solution cost peaks around the transition, with approximately 42% of variables preassigned [Gomes and Selman, 1997].

We encoded the problem in ILOG Solver, a C++ con­ straint toolkit which includes Regin's algorithm for main­ taining GAC on all-different constraints. We used the Bre­ laz heuristic for variable selection (as in [Gomes and Sel­ man, 1997]) and Geelen's promise heuristic for value order­ ing (as in [Meseguer and Walsh, 1998]). Gomes et al. ob­ served that search costs to solve random quasigroup comple­ tion problems can be modeled by a "heavy-tailed" distribu­ tion [Gomes et al., 1997]. We therefore focus on the higher percentiles. Table 1 gives branches explored to complete an order 10 quasigroup with p% of entries preassigned, main­ taining either AC on the binary representation or GAC on the all-different constraints. We see a very significant advantage for MGAC over MAC. With a random value ordering, the worst case for MGAC was also 2 branches. CPU times re­ flect the difference in explored branches. For example, some instances at the phase transition for quasigroups of order 20 were solved by MGAC in seconds, while MAC took hours.

Table 2 shows that, as we increase problem size, almost all the problems remain trivial. The only exception was a single order 25 problem with 42% of its variables preas­ signed. Search was abandoned at the cuttoff limit of 10,000 branches. Apart from this, all instances were solved in less than 5 branches. This is a significant improvement over the results of [Gomes et al. , 1997] where, despite the use of ran­ dom restarts, problems of order 25 were too expensive to solve, especially at the phase transition.

6.2 Quasigroup existence

A variety of automated reasoning programs have been used to answer open questions in finite mathematics about the exis­ tence of quasigroups with particular properties [Fujita et al., 1993]. Is GAC useful on these problems? We follow [Fujita et al. , 1993] and look at the so-called QG3, QG4, QG5, QG6 and QG7 class of problems. For example, the QG5 problems concern the existence of idempotent quasigroups (those in which a· a = a for each element a) in which ( ba ·b) b = a. For the definition of the other problems, see [Fujita et al. , 1993]. In these problems, the structure of the constraint graph is dis­ turbed by additional non-binary constraints. These reduce the level of consistency achieved compared to quasigroup com­ pletion problems. Nevertheless, GAC significantly prunes the search space and reduces runtimes.

To solve these problems, we again use the Solver toolkit, maintaining either GAC on the all-different constraints, or AC on the binary representation, and the fail -first heuristic for variable ordering. To eliminate some of the symmetric models, as in [Fujita et al. , 1993], we added the constraint that a · n ~ a - 1 for every element a. Table 3 demon­ strates the benefits of MGAC over MAC. In QG3 and QG4, MAC explores twice as many branches as MGAC, in QG5 the difference is orders of magnitude, whilst there is only a slight difference in QG6 and QG7. MGAC dominates MAC in terms of CPU time as well as in terms of explored branches. It would be interesting to identify the features of QG5 that gives MGAC such an advantage over MAC, and those of QG6 and QG7 that lessen this advantage.

We now compare our results with those of FINDER [Slaney, 1992], MACE [McCune, 1994], MGTP [Fujita et al., 1993], SATO [Zhang and M., 1994], and SEM [Zhang and Zhang, 1995]. Table 4 shows that Solver outperforms MGTP and FINDER by orders of magnitude, and explores less branches than SEM. SEM and SATO have sophisticated branching heuristics and complex rules for the symmetry breaking that are far more powerful than the symmetry break­ ing constraint we use [Zhang and Zhang, 1995]. It is there­ fore impressive that our simple Solver program is competitive with well-developed systems like SEM and SATO.

To conclude, despite the addition of non-binary constraints that disturb the structure of the constraint graph, MGAC sig­ nificantly reduces search and runtimes on quasigroup exis­ tence problems. We conjecture that the performance of SEM and SATO could be improved by the addition of a specialized procedure to maintain GAC on the all-different constraints.

6.3 Small-worlds problems

Recently, [Watts and Strogatz, 1998] has shown that graphs that occur in many biological, social and man-made systems are often neither completely regular nor completely random, but have instead a "small world" topology in which nodes are highly clustered, whilst the path length between them is small. Walsh has argued that such a topology can make search problems hard since local decisions quickly propagate glob­ ally [Walsh, 1999]. To construct graphs with such a topology, we start from the constraint graph of a structured problem like a quasigroup and introduce randomness by deleting edges at random from the binary representation. Deleting an edge at random breaks up an all-different constraint on n variables into two all-different constraints on n - 1 variables. For ex­ ample, if x1 , x 2 , x3 ... , Xk are all-different and remove the edge between x 1 and x 2 then we are left with all-different constraints on x 1, x3 ... , Xk and x2, x 3 ... , Xk -

Figures 2 and 3 show percentiles in the number of branches explored and in CPU time to find the optimal coloring of or­ der 10 quasigroups in which we delete p% of edges from the binary representation. The hardest problems had 5% of their edges removed. MGAC dominates MAC by orders of mag­ nitude in the hard region both in terms of branches explored and CPU time. All instances were solved by MGAC within 120 seconds while approximately 10% of the instances could not be solved by MAC within 1 hour. As p increases, prob­ lems become very easy and both MGAC and MAC quickly find a solution. MAC starts to outperform MGAC in terms of CPU time as the overhead of GAC on the large number of all-different constraints is greater.

7 Related work

[Gomes and Selman, 1997] solved quasigroup completion problems using the MAC algorithm and a binary represen­ tation. They found that a randomization and restart strategy could eliminate the heavy-tailed behavior of the backtracking algorithm. However, they were still not able to consistently solve quasigroup completion problems of order 25 or larger.

[Meseguer and Walsh, 1998] solved quasigroup comple­ tion problems using forward checking (FC) on the binary representation. They found that discrepancy and interleaved based methods can reduce the heavy tail. However, their ex­ periments were limited to quasigroups of order 20 and less.

[Bacchus and van Beek, 1998] have compared generalized FC on non-binary constraints with FC on the hidden variable and dual encodings into binary constraints. They show that a simple extension of FC on the hidden variable encoding dominates generalized FC on the non-binary representation.

8 Conclusions

We have shown experimentally and theoretically the bene­ fits of achieving generalized arc-consistency on decompos­ able constraints like all-different constraints. Generalized arc-consistency on such constraints lies between neighbor­ hood inverse consistency and, under a simple restriction, path inverse consistency on the binary representation of the prob­ lem. On quasigroup completion problems, generalized arc­ consistency achieves neighborhood inverse consistency. By generalizing the arguments of [Kondrak and van Beek, 1997], we proved that a search algorithm that maintains generalized arc-consistency on decomposable constraints dominates a search algorithm that maintains arc-consistency on the binary representation. Our generalization also proves the correctness of the algorithms that maintain arc-consistency or generalized arc-consistency. Our experiments demonstrated the practical value of achieving these high levels of consistency. For exam­ ple, we solved almost all benchmark quasigroup completion problems up to order 25 with just a few branches of search. On quasigroup existence problems, we are competitive with the best programs, despite lacking their specialized branching heuristics and symmetry breaking rules.

What general lessons can be learnt from this study? First, it can be very beneficial to identify structure in a problem by means of a non-binary representation. We can use this structure to enforce higher levels of consistency than can be practical in a binary representation. Second, theory can be motivated by experiment. We were led to attempt our the­ oretical analysis by the exceptionally good experimental re­ sults on quasigroup completion problems. And finally, the all-different constraint really can make a big difference.