Refining the Basic Constraint Propagation Algorithm

1 Introduction

Constraint propagation is the basic operation in constraint programming. It is now well-recognized that its extensive use is necessary when we want to efficiently solve hard constraint satisfaction problems. All the constraint solvers use it as a basic step. Thus, each improvement that can be incorporated in a constraint propagation algorithm has an immediate effect on the behavior of the constraint solving engine. In practical applications, many constraints are of well-known types for which specific algorithms are available. These algorithms generally receive a set of removed values for one of the variables involved in the constraint, and propagate these deletions according to the constraint. They are usually as cheap as one can expect in cpu time. This state of things implies that most of the existing solving engines are based on a constraint-oriented or variable-oriented propagation scheme (ILOG Solver, CHOCO, etc.). And AC-3, with its natural both constraint-oriented [Mackworth, 1977] and variable-oriented [McGregor, 1979] propagation of the constraints, is the generic constraint propagation algorithm which fits the best this propagation scheme. Its successors, AC-4, AC-6, and AC-7, indeed, were written with a valueoriented propagation. This is one of the reasons why AC-3 is the algorithm which is usually used to propagate those constraints for which nothing special is known about the semantics (and then for which no specific algorithm is available). This algorithm has a second strong advantage when compared to AC-4, AC-6 or AC-7, namely, its independence with regard to specific data structure which should be maintained if used during a search procedure. (And following that, a greater easiness to implement it.) On the contrary, its successors, while more efficient when applied to networks where much propagation occurs ([Bessière et al., 1995; Bessière et al., 1999]), need to maintain some additional data structures.

1 This work has been partially financed by ILOG under a research collaboration contract ILOG/CNRS/University of Montpellier II.

2 Member of the COCONUT group.

In this paper, our purpose is to present two new algorithms, AC2000 and AC2001, which, like AC-3, accept variableoriented and constraint-oriented propagation, and which improve AC-3 in efficiency (both in terms of constraint checks and cpu time). AC2000, like AC-3, is free of any data structure to be maintained during search. AC2001, at the price of a slight extra data structure (just an integer for each valueconstraint pair) reaches an optimal worst-case time complexity. 3 It leads to substantial gains, which are shown both on randomly generated and real-world instances of problems. A comparison with AC-6 shows interesting theoretical properties. Regarding the human cost of their implementation, AC2000 needs a few lines more than the classical AC-3, and AC2001 needs the management of its additional data structure.

2 Preliminaries

Constraint network. A finite binary constraint network P = (X;;D;; C) is defined as a set of n variables X = fX 1 ;; : : : ;; X n g, a set of domains D = fD(X 1 );; : : : ;; D(X n )g, where D(X i ) is the finite set of possible values for variable X i , and a set C of e binary constraints between pairs of variables. A constraint C ij on the ordered set of variables (X i ;; X j ) is a subset of the Cartesian product D(X i )-D(X j ) that specifies the allowed combinations of values for the variables X i and X j . (For each constraint C ij , a constraint C ji is defined between (X j ;;X i ), allowing the same pairs of values in the reverse order.) Verifying whether a given pair (v i ;; v j ) is allowed by C ij or not is called a constraint check. A solution of a constraint network is an instantiation of the variables such that all the constraints are satisfied.

3 A related paper by Zhang and Yap appears in these proceedings.

Arc consistency. Let P = (X;;D;; C) be a constraint network, and C ij a constraint in C. A value v i 2 D(X i ) is consistent with C ij iff 9v j 2 D(X j ) such that (v i ;; v j ) 2 C ij . (v j is then called a support for (X i ;; v i ) on C ij .) A value v i 2 D(X i ) is viable iff it has support in all D(X j ) such that C ij 2 C. P is arc consistent iff all the values in all the domains are viable. We achieve arc consistency in P by removing every value which is not viable.

3 A first stab at improving AC-3

3.1 Background on AC-3

Before presenting the algorithmwe propose in this section, let us briefly recall the AC-3 algorithm. We present it with the structure proposed by McGregor [McGregor, 1979], which is built on a variable-based propagation scheme. This will be recommended for the algorithm presented in the next subsection. The main algorithm (see Algorithm 1) is very close to the original AC-3, with an initialization phase (lines 1 to 3), a propagation phase (line 4), and with the use of the function Revise3(X i ;;X j ) that removes from D(X i ) the values without support in D(X j ) (line 2). But instead of handling a queue of the constraints to be propagated, it uses a queue 4 of the variables that have seen their domain modified. When a variable X j is picked from the queue (line 2 of Propagation3 in Algorithm 2), all the constraints involving X j are propagated with Revise3. This is the only change w.r.t. the Mackworth's version of AC-3. 5 (This algorithm has been presented in [Chmeiss and Jégou, 1998] under the name AC-8.)

Algorithm 1: Main algorithm

functionAC (in X: set): Boolean if D(X i ) = ;; then return false ;

1 Q ;;; for each X i 2 X do for each X j such that C ij 2 C do 2 if Revise-X(X i ;;X j ;; false 6 ) then 3 Q Q[ fX i g; 4 return Propagation-X(Q);

3.2 The algorithm AC2000

If we closely examine the behavior of AC-3, we see that removing a single value v j from a domain D(X j ) (inside function Revise3) is enough to put X j in the propagation queue

4 We name it a queue, but, as in AC-3, it has to be implemented as a set since in line 3 of Algorithm 1 and in line 5 of Algorithm 2 we add X i to Q only if it does not already belong to it.

5 In fact, McGregor's version of the function Revise differs from Mackworth's one. Algorithm Revise3 is the Mackworth's version [Mackworth, 1977].

6 The third parameter is useless for AC-3 but will be used in the next version of Revise.

Algorithm 2: Subprocedures for AC-3

function Propagation3 (in Q: set): Boolean 1 while Q6= ;; do 2 pick X j fromQ; 3 for each X i such that C ij 2 C do 4 if Revise-X(X i ;;X j ) then if D(X i ) = ;; then return false ; 5 Q Q[ fX i g; return true ; function Revise3 (in X i ;; X j : variable): Boolean CHANGE false; for each v i 2 D(X i ) do if 6 9v j 2 D(X j )=C ij (v i ;; v j ) then remove v i fromD(X i ); CHANGE true; return CHANGE ;

(line 3 of AC in Algorithm 1 and line 5 of Propagation3 in Algorithm 2), and to provoke a call to Revise3(X i ;;X j ) for every constraint C ij involving X j (lines 3 and 4 of Propagation3). Revise3 will look for a support for every value in D(X i ) whereas for some of them v j was perhaps not even a support. (As a simple example, we can take the constraint X i = X j , where D(X i ) = D(X j ) = [1::11]. Removing value 11 from D(X j ) leads to a call to Revise3(X i ;;X j ), which will look for a support for every value in D(X i ), for a total cost of 1+2+: : :+9+10+10 = 65 constraint checks, whereas only (X i ;; 11) had lost support.) We exploit this remark in AC2000. Instead of looking blindly for a support for a value v i 2 D(X i ) each time D(X j ) is modified, we do that only under some conditions. In addition to the queue Q of variables modified, we use a second data structure,
(X j ), 7 which for each variable X j contains the values removed since the last propagation of X j . When a call to Revise2000(X i ;;X j ;; lazymode) is performed, instead of systematically looking whether a value v i still has support in D(X j ), we first check that v i really lost a support, namely one of its supports is in
(X j ) (line 3 of Revise2000 in Algorithm 3). The larger
(X j ) is, the more expensive that process is, and the greater the probability to actually find a support to v i in this set is. So, we perform this "lazymode" only if
(X j ) is sufficiently smaller than D(X j ). We use a parameter Ratio to decide that. (See line 1 of Propagation2000 in Algorithm 3.) The Boolean lazymode is set to true when the ratio is not reached. Otherwise, lazymode is false, and Revise2000 performs exactly as Revise3, going directly to lines 4 to 5 of Revise2000 without testing the second part of line 3.

If we run AC2000 on our previous example, we have
(X j ) = f11g. If j
(X j )j < Ratio
jD(X j )j, then for each v i 2 D(X i ), we check whether
(X j ) contains a support of v i before looking for a support for v i . This requires 11 constraint checks. The only value for which support is effectively sought is (X i ;; 11). That requires 10 additional

7 We take this name from [Van Hentenryck et al., 1992], where
denotes the same thing, but for a different use.

function Propagation2000 (in Q: set): Boolean while Q 6= ;; do pick X j fromQ; 1 lazymode (j
(X j )j < Ratio 
 jD(X j )j); for each X i such that C ij 2 C do if Revise2000(X i ;; X j ;; lazymode) then if D(X i ) = ;; then return false ; Q Q[ fX i g; 2 reset 
(X j ); return true ; function Revise2000 (in X i ;; X j : variable; in lazymode: Boolean ): Boolean CHANGE false; for each v i 2 D(X i ) do 3 if :lazymode or 9v j 2 
(X j )=C ij (v i ;; v j ) then 4 if 6 9v j 2 D(X j )=C ij (v i ;; v j ) then remove v i fromD(X i ); add v i to 
(X i ); 5 CHANGE true; return CHANGE ;

constraint checks. We save 44 constraint checks compared to AC-3.

Analysis

Let us first briefly prove AC2000 correctness. Assuming AC-3 is correct, we just have to prove that the lazy mode does not let arc-inconsistent values in the domain. The only way the search for support for a value v i in D(X i ) is skipped, is when we could not find a support for v i in
(X j ) (line 3 of Revise2000). Since
(X j ) contains all the values deleted from D(X j ) since its last propagation (line 2 of Propagation2000), this means that v i has exactly the same set of supports as before on C ij . Thus, looking again for a support for v i is useless. It remains consistent with C ij .

The space complexity of AC2000 is bounded above by the sizes of Q and
. Q is in O(n) and
is in O(nd), where d is the size of the largest domain. This gives a O(nd) overall complexity. In this space complexity, it is assumed that we built AC2000 with the variable-oriented propagation scheme, as recommended earlier. If we implement AC2000 with the constraint-oriented propagation scheme of the original AC-3, we need to attach a
(X j ) to each constraint C ij put in the queue. This implies a O(ed) space complexity.

The organization of AC2000 is the same as in AC-3. The main change is in function Revise2000, where
(X j ) and D(X j ) are examined instead of only D(X j ). Their total size is bounded above by d. This leads to a worst-case where d 2 checks are performed, as in Revise3. Thus, the overall time complexity is in O(ed 3 ) since Revise2000 can be called d times per constraint. This is as in AC-3.

4 AC2001

In Section 3, we proposed an algorithm, which, like AC-3, does not need special data structures to be maintained during search. (Except the current domains, which have to be maintained by any search algorithm performing some lookahead.) During a call to Revise2000, for each v i in D(X i ), we have to look whether v i has a support in
(X j ), to know whether it lost supports or not. In this last case, we have to look again for a support for v i on C ij in the whole D(X j ) set. If we could remember what was the support found for v i in D(X j ) the last time we revised C ij , the gain would be twofold: First, we would just have to check whether this last support has been removed fromD(X j ) or not, instead of exploring the set
(X j ). Second, when a support was effectively removed from D(X j ), we would just have to explore the values in D(X j ) that are "after" that last support since "predecessors" have already been checked before. Adding a very light extra data structure to remember the last support of a value on a constraint leads to the algorithm AC2001 that we present in this section.

Let us store in Last(X i ;; v i ;;X j ) the value that has been found as a support for v i at the last call to Revise2001(X i ;;X j ). The function Revise2001 will always run in the lazy mode since the cost of checking whether the Last support on C ij of a value v i has been removed from D(X j ) is not dependent on the number of values removed from D(X j ). A second change w.r.t. AC2000 is that the structure
is no longer necessary since the test "Last(X i ;; v i ;;X j ) 62 D(X j )" can replace the test "Last(X i ;; v i ;;X j ) 2
(X j )". The consequence is that AC2001 can equally be used with a constraintbased or variable-based propagation. We only present the function Revise2001, which simply replaces the function Revise3 in AC-3. The propagation procedure is that of AC-3, and the Last structure has to be initialized to NIL at the beginning. In line 1 of Revise2001 (see Algorithm 4) we check whether Last(X i ;; v i ;;X j ) still belongs to D(X j ). If it is not the case, we look for a new support for v i in D(X j ); otherwise nothing is done since Last(X i ;; v i ;;X j ) is still in D(X j ). In line 2 of Revise2001 we can see the second advantage of storing Last(X i ;; v i ;;X j ): If the supports are checked in D(X j ) in a given ordering "< d ", we know that there isn't any support for v i before Last(X i ;; v i ;;X j ) in D(X j ). Thus, we can look for a new support only on the values greater than Last(X i ;; v i ;; X j ).

function Revise2001 (in X i ;; X j : variable): Boolean CHANGE false; for each v i 2 D(X i ) do 1 if Last(X i ;; v i ;;X j ) 62 D(X j ) then 2 if 9v j 2 D(X j )=v j > d Last(X i ;; v i ;; X j )^C ij (v i ;; v j ) then Last(X i ;; v i ;;X j ) v j ; else remove v i fromD(X i ); add v i to
(X i ); CHANGE true; return CHANGE ;

On the example of Section 3, when (X j ;; 11) is removed, AC2001 simply checks for each v i 2 [1::10] that Last(X i ;; v i ;;X j ) still belongs to D(X j ), and finds that Last(X i ;; 11;; X j ) has been removed. Looking for a new support for 11 does not need any constraint check since D(X j ) does not contain any value greater than Last(X i ;; 11;;X j ), which was equal to 11. It saves 65 constraint checks compared to AC-3.

Analysis

Proving correctness of AC2001 can be done very quickly since the framework of the algorithm is very close to AC-3. They have exactly the same initialization phase except that AC2001 stores Last(X i ;; v i ;;X j ), the support found for each v i on each C ij . (In line 1 it is assumed that NIL does not belong to D(X j ).) During the propagation, they diverge in the way they revise an arc. As opposed to AC-3, Revise2001(X i ;;X j ) goes into a search for support for a value v i in D(X i ) only if Last(X i ;; v i ;;X j ) does not belong to D(X j ). We see that checking that Last(X i ;; v i ;;X j ) still belongs to D(X j ) is sufficient to ensure that v i still has a support in D(X j ). And if a search for a new support has to be done, limiting this search to the values of D(X j ) greater than Last(X i ;; v i ;;X j ) w.r.t. to the ordering < d used to visit D(X j ) is sufficient. Indeed, the previous call to Revise2001 stopped as soon as the value Last(X i ;; v i ;; X j ) was found. It was then the smallest support for v i in D(X j ) w.r.t. < d .

The space complexity of AC2001 is bounded above by the size of Q, and Last. Q is in O(n) or O(e), depending on the propagation scheme that is used (variable-based or constraintbased). Last is in O(ed) since each value v i has a Last pointer for each constraint involving X i . This gives a O(ed) overall complexity.

As in AC-3 and AC2000, the function Revise2001 can be called d times per constraint in AC2001. But, at each call to Revise2001(X i ;;X j ), for each value v i 2 D(X i ), there will be a test on the Last(X i ;; v i ;;X j ), and a search for support only on the values of D(X j ) greater than Last(X i ;; v i ;;X j ). Thus, the total work that can be performed for a value v i over the d possible calls to Revise2001 on a pair (X i ;;X j ) is bounded above by d tests on Last(X i ;; v i ;; X j ) and d constraint checks. The overall time complexity is then bounded above by d
(d+d)
2
e, which is in O(ed 2 ). This is optimal [Mohr and Henderson, 1986]. AC2001 is the first optimal arc consistency algorithm proposed in the literature that is free of any lists of supported values. Indeed, the other optimal algorithms, AC-4, AC-6, AC-7, and AC-Inference all use these lists.

5 Experiments

In the sections above, we presented two refinements of AC-3, namely AC2000 and AC2001. It remains to see whether they are effective in saving constraint checks and/or cpu time when compared to AC-3. AS we said previously, the goal is not to compete with AC-6/AC-7, which have very subtle data structure for the propagation phase. An improvement (even small) w.r.t. AC-3 would fulfill our expectations. However, we give AC-6 performances, just as a marker.

5.1 Arc consistency as a preprocessing

The first set of experiments we performed should permit to see the effect of our refinements when arc consistency is used as a preprocessing (without search). In this case, the chance to have some propagations is very small on real instances. We have to fall in the phase transition of arc consistency (see [Gent et al., 1997]). So, we present results for randomly generated instances (those presented in [Bessière et al., 1999]), and for only one real-world instance. For the random instances, we used a model B generator [Prosser, 1996]. The parameters are < N;; D;; C=p1;; T=p2 >, where N is the number of variables, D the size of the domains, C the number of constraints (their density p1 = 2C=N
(N ; 1)), and T the number of forbidden tuples (their tightness p2 = T=D 2 ). The real-world instance, SCEN#08, is taken from the FullRLFAP archive, 8 which contains instances of radio link frequency assignment problems (RLFAPs). They are described in [Cabon et al., 1999]. The parameter Ratio used in AC2000 is set to 0.2. Table 1 presents the results for four classes of random instances plus the real-world one.

The upper two are under-constrained (<150;; 50;; 500=0:045;; 1250=0.5>) and over-constrained (<150;; 50;; 500=0:045;; 2350=0.94>) problems. They represent cases where there is little or no propagation to reach the arc consistent or arc inconsistent state. This is the best case for AC-3, which performs poorly during propagation. We can see that AC2000 and AC2001 do not suffer from this.

The third and fourth experiments are at the phase transition of arc consistency for sparse (<150;; 50;; 500=0.045;; 2296=0:918>) and dense (<50;; 50;; 1225=1.0;; 2188=0:875>) problems. We can assume there is much propagation on these problems before reaching the arc consistent state. This has a significant impact on the respective efficiencies of the algorithms. The smarter the algorithm is, the lower the number of constraint checks is. AC2001 dominates AC2000, which itself dominates AC-3. And the cpu time follows this trend.

8 We thank the Centre d'Electronique de l'Armement (France).

The lower experiment reports the results for the SCEN#08. This is one of the instances in FullRLFAP for which arc consistency is sufficient to detect inconsistency.

5.2 Maintaining arc consistency during search

The second set of experiments we present in this section shows the effect of our refinements when arc consistency is maintained during search (MAC algorithm [Sabin and Freuder, 1994]) to find the first solution. We present results for all the instances contained in the FullRLFAP archive for which more than 2 seconds were necessary to find a solution or prove that none exists. We took again 0.2 for the Ratio in AC2000. It has to be noticed that the original question in these instances is not satisfiability but the search of the "best" solution, following some criteria. It is of course out of the scope of this paper.

From these instances we can see a slight gain for AC2000 on AC-3. On SCEN#11, it can be noticed that with a smaller Ratio, AC2000 slightly improves its performances. (Ratio = 0.05 seems to be the best.) A more significant gain can be seen for AC2001, with up to 9 times less constraint checks and twice less cpu time on SCEN#11. As for the experiments performed on random instances at the phase transition of arc consistency, this tends to show that the trick of storing the Last data structure significantly pays off. However, we have to keep in mind that we are only comparing algorithms with simple data structures. This prevents them from reaching the efficiency of algorithms using lists of supported values when the amount of propagation is high, namely on hard problems. (E.g., a MAC algorithm using AC-6 for enforcing arc consistency needs only 14.69 seconds to solve the SCEN#11 instance.)

6 AC2001 vs AC-6

In the previous sections, we proposed two algorithms based on AC-3 to achieve arc consistency on a binary constraint network. AC2000 is close to AC-3, from which it inherits its O(ed 3 ) time complexity and its O(nd) space complexity. AC2001, thanks to its additional data structure, has an optimal O(ed 2 ) worst-case time complexity, and an O(ed) space complexity. These are the same characteristics as AC-6. 9 So, we can ask the question: "What are the differences between AC2001 and AC-6?".

9 We do not speak about AC-7 here, since it is the only one among these algorithms to deal with the bidirectionality of the constraints

Let us first briefly recall the AC-6 behavior [Bessière, 1994]. AC-6 looks for one support (the first one or smallest one with respect to the ordering < d ) for each value (X i ;; v i ) on each constraint C ij to prove that (X i ;; v i ) is currently viable. When (X j ;; v j ) is found as the smallest support for (X i ;; v i ) on C ij , (X i ;; v i ) is added to S[X j ;; v j ], the list of values currently having (X j ;; v j ) as smallest support. If (X j ;; v j ) is removed from D(X j ), it is added to the DeletionSet, which is the stream driving propagations in AC-6. When (X j ;; v j ) is picked from the DeletionSet, AC-6 looks for the next support (i.e., greater than v j ) in D(X j ) for each value (X i ;; v i ) in S[X j ;; v j ]. Notice that the DeletionSet corresponds to P X j 2X
(X j ) in AC2000, namely the set of values removed but not yet propagated.

To allow a closer comparison, we will suppose in the following that the S[X i ;; v i ] lists of AC-6 are split on each constraint C ij involving X i , leading to a structure S[X i ;; v i ;;X j ], as in AC-7.

Property 1 Let P = (X;;D;; C) be a constraint network. If we suppose AC2001 and AC-6 follow the same ordering of variables and values when looking for supports and propagating deletions, then, enforcing arc consistency on P with AC2001 requires the same constraint checks as with AC-6.

Proof. Since they follow the same ordering, both algorithms perform the same constraint checks in the initialization phase: they stop search for support for a value v i on C ij as soon as the first v j in D(X j ) compatible with v i is found, or when D(X j ) is exhausted (then removing v i ). During the propagation phase, both algorithms look for a new support for a value v i on C ij only when v i has lost its current support v j in D(X j ) (i.e., v i 2 S[X j ;; v j ;;X i ] for AC-6, and v j = Last(X i ;; v i ;;X j ) for AC2001). Both algorithms start the search for a new support for v i at the value in D(X j ) immediately greater than v j w.r.t. the D(X j ) ordering. Thus, they will find the same new support for v i on C ij , or will remove v i , at the same time, and with the same constraint checks. And so on. 2

From property 1, we see that the difference between AC2001 and AC-6 cannot be characterized by the number of constraint checks they perform. We will then focus on the way they find which values should look for a new support. For that, both algorithms handle their specific data structures. Let us characterize the number of times each of them checks

its own data structure when a set
(X j ) of deletions is propagated on a given constraint C ij .

Property 2 Let C ij be a constraint in a network P = (X ;; D;; C). Let
(X j ) be a set of values removed from D(X j ) that have to be propagated on C ij . If,

C = # checks performed on C ij to propagate
(X j ), then, A + C and B + C represent the number of operations AC-6 and AC2001 will respectively perform to propagate
(X j ) on C ij .

Proof. From property 1 we know that AC-6 and AC2001 perform the same constraint checks. The difference is in the process leading to them. AC-6 traverses the S[X j ;; v j ;;X i ] list for each v j 2
(X j ) (i.e., A operations), and AC2001 checks whether Last(X i ;; v i ;; X j ) belongs to D(X j ) for every v i in D(X i ) (i.e., B operations). 2

We illustrate this on the extreme case presented in Figure 1. In that example, the three values of X i are all compatible with the first value v 0 of X j . In addition, (X i ;; v 1 ) is compatible with all the values of X j from v 1 to v 50 , and (X i ;; v 2 ) with all the values of X j from v 51 to v 100 . Imagine that for some reason, the value v 3 has been removed from D(X i ) (i.e.,
(X i ) = fv 3 g). This leads to A = 1, B = 101, and C = 0, which is a case in which propagating with AC-6 is much better than with AC2001, even if none of them needs any constraint check. Indeed, AC-6 just checks that S[X i ;; v 3 ;;X j ] is empty, 10 and stops. AC2001 takes one by one the 101 values v j of D(X j ) to check that their Last(X j ;; v j ;;X i ) is not in
(X i ). Imagine now that the values v 1 to v 100 of D(X j ) have been removed (i.e.,
(X j ) = fv 1 ;; : : : ;; v 100 g). Now, A = 100, B = 3, and C = 0. This means that AC2001 will clearly outperformAC-6. Indeed, AC-6 will check for all the 100 values v j in
(X j ) that S[X j ;; v j ;;X i ] is empty, 11 while AC2001 just checks that Last(X i ;; v i ;;X j ) is not in
(X j ) for the 3 values in D(X i ).

10 The only value compatible with (X i ;; v 3 ) is (X j ;; v 0 ), which is currently supported by (X i ;; v 1 ).

Discussion

Thanks to property 2, we have characterized the amount of effort necessary to AC-6 and AC2001 to propagate a set
(X j ) of removed values on a constraint C ij . A;B gives us information on which algorithm is the best to propagate
(X j ) on C ij . We can then easily imagine a new algorithm, which would start with an AC-6 behavior on all the constraints, and would switch to AC2001 on a constraint C ij as soon as A ; B would be positive on this constraint (and then forget the S lists on C ij ). Switching from AC2001 to AC-6 is no longer possible on this constraint because we can deduce in constant time that Last(X i ;; v i ;;X j ) = v j when v i belongs to S[X j ;; v j ;;X i ], but we cannot obtain cheaply S[X j ;; v j ;;X i ] from the Last structure. A more elaborated version would maintain the S lists even in the AC2001 behavior (putting v i in S[X j ;; v j ;;X i ] each time v j is found as being the Last(X i ;; v i ;;X j )). This would permit to switch from AC-6 to AC2001 or the reverse at any time on any constraint in the process of achieving arc consistency. These algorithms are of course far from our initial purpose of emphasizing easiness of implementation since they require the S and Last structures to be maintained during search.

7 Non-binary versions

Both AC2000 and AC2001 can be extended to deal with non-binary constraints. A support is now a tuple instead of a value. Tuples in a constraint C(X i 1 ;; : : : ;;X i q ) are ordered w.r.t. the ordering < d of the domains, combined with the ordering of X i 1 ;; : : : ;;X i q (or any order used when searching for support). Once this ordering is defined, a call to Revise2000(X i ;;C) -because of a set
(X j ) of values removed from D(X j )- simply checks for each v i 2 D(X i ) whether there exists a support  of v i on the constraint C for which [X j ] (the value of X j in the tuple) belongs to
(X j ). If yes, it looks for a new support for v i on C. Revise2001(X i ;;C) checks for each v i 2 D(X i ) whether Last(X i ;; v i ;;C), which is a tuple, still belongs to D(X i 1 ) -


-D(X i q ) before looking for a new support for v i on C.

This extension to non-binary constraints is very simple to implement. However, it has to be handled with care when the variable-oriented propagation is used, as recommended for AC2000. (With a constraint-based propagation, a
(X j ) set is duplicated for each constraint put in the queue to propagate it.) Variable-based propagation is indeed less precise in the way it drives propagation than constraint-based propagation. Take the constraint C(X i 1 ;;X i 2 ;;X i 3 ) as an example. If D(X i 1 ) and D(X i 2 ) are modified consecutively, X i 1 and X i 2 are put in the queue Q consecutively. Picking X i 1 from Q implies the calls to Revise(X i 2 ;; C) and Revise(X i 3 ;; C), and picking X i 2 implies the calls to Revise(X i 1 ;;C) and Revise(X i 3 ;;C). We see that Revise(X i 3 ;;C) is called twice while once was enough. To overcome this weakness, we need to be more precise in the way we propagate deletions. The solution, while being technically simple, is more or less dependent on the architecture of the solver in which it is used. Standard techniques are described in [ILOG, 1998; Laburthe, 2000].

11 Indeed, (X j ;; v 0 ) is the current support for the three values in D(X i ) since it is the smallest in D(X j ) and it is compatible with every value in D(X i ).

8 Conclusion

We presented AC2000 and AC2001, two refinements in AC-3. The first one improves slightly AC-3 in efficiency (number of constraint checks and cpu time) although it does not need any new data structure to be maintained during search. The second, AC2001, needs an additional data structure, the Last supports, which should be maintained during search. This data structure permits a significant improvement on AC-3, and decreases the worst-case time complexity to the optimal O(ed 2 ). AC2001 is the first algorithm in the literature achieving optimally arc consistency while being free of any lists of supported values. Its behavior is compared to that of AC-6, making a contribution to the understanding of the different AC algorithms, and opening an opportunity of improvement. This is in the same vein as the work on AC-3 vs AC-4 [Wallace, 1993], which was leading up to AC-6.

Acknowledgements

We would like to thank Philippe Charman who pointed out to us the negative side of value-oriented propagation. The first author also wants to thank all the members of the OCRE team for the discussions we had about the specification of the CHOCO language.