Using Inference to Reduce Arc Consistency Computation

1 Introduction

1.1 Overview

Constraint satisfaction problems ( CSPs) occur widely in artificial intelligence. They involve finding values for problem variables subject to constraints on which com­ binations are acceptable. For simplicity we restrict our attention here to binary CSPs, where the constraints in­ volve two variables.

Binary constraints are binary relations. If a variable i has a domain of potential values Di and a variable j has a domain of potential values D1, the constraint on i and j, Rij, is a subset of the Cartesian product of Di and D j. If the pair of values a for i (denoted by ( i, a)) and b for j (denoted by (j, b)) is acceptable to the constraint Rij between i and j, i.e. a member of the Cartesian product, we will call the values consistent (with respect to ~j). Asking whether a pair of values is consistent is called a constraint check.

Constraints can be represented implicitly, where a computation, or a real-world process, is needed to an­ swer constraint check questions, or explicitly, where the

Jean-Charles Regin

GDR 1093 CNRS, LIRMM, 161 rue Ada 34392 Montpellier cedex 5, France

phone: (33) 67 41 85 80

fax: (33) 67 41 85 00

e-mail: reginCilirmm. fr

answer is already recorded in a data base. Implicit con­ straint checks could be very costly to compute. Even if the constraints are represented explicitly in a form that permits quick computation there may be an enor­ mous number to compute, along with associated deci­ sions about which checks to make and how to use the results. As a result much of the work on constraint rea­ soning has focused on ways to reduce the number of con­ straint checks required.

Constraint algorithms often seek to establish support for a value a E Di, i.e . . to find a value for a variable j that is consistent with (i, a) (or to determine that no such value exists). Traditionally constraint checks have been used to establish support. This paper proposes to reduce constraint checks by using metalevel knowledge to infer support. We will demonstrate that one such infer­ ence can save many additional constraint checks, ensur­ ing that the benefits of these inferences can more than offset the costs associated with making and exploiting them.

We apply this approach to building a schema for arc consistency algorithms. Arc consistency is one of the most basic and useful constraint reasoning processes. Thus arc consistency algorithms have been the subject of much interest [Mackworth and Freuder, 1993]. The new algorithm schema, AC-Inference, permits use of inferred support. We identify several properties of constraints that permit such inferences. We hope that AC-Inference will permit the exploitation of many other generic and problem domain specific properties of constraints. Fur­ thermore, the metaknowledge inference approach should also be extensible to higher order consistency [Freuder, 1978].

We refine the schema to build a specific, new arc con­ sistency algorithm AC-7. AC-7 is a general arc con­ sistency algorithm, since it does not depend on special properties of a limited class of constraints, but simply utilizes the knowledge that support is bidirectional: (i , a) supports (j, b) if and only if (j, b) supports (i, a). (It is tempting to assume that a special class of undirected constraints is required here; but a careful reading of [Mackworth, 1977] should demonstrate that this is not the case.)

AC-Ts exploitation of bidirectionality gives it a com­ putational advantage over other general purpose arc con­ sistency algorithms, and restricting attention to bidirectionality also permits an implementation with space effi­ ciency comparable to the best of these algorithms, which is not possible for the AC-Inference schema in general. Constraint programmers tell us that space can be a ma­ jor issue for practical applications. On the other hand, AC-Inference permits us to obtain additional computa­ tional efficiency by taking advantage of knowledge about a restricted class of constraints. We demonstrate each of these advantages experimentally in real-world applica­ tions. We also provide analytical evaluation of AC-7, specifically refuting an optimality claim for an earlier algorithm, AC-6 [Bessiere and Cordier, 1993].

1.2 Relation to Previous Work

For some time the state of the art resided in two algo­ rithms, AC-4 [Mohr and Henderson, 1986], which has op­ timal worst-case behavior, and AC-3 [Mackworth, 1977], which often exhibits better average-case behavior [Wal­ lace, 1993]. Two AC-5 algorithms, one by Deville and Van Hentenryck [Deville and Hentenryck, 1991] and an­ other by Perlin [Perlin, 1992], permit exploitation of cer­ tain specific constraint structures, but reduce to AC-3 or AC-4 in the general case. Recently Bessiere and Cordier have developed AC-6, which retains the opti­ mal worst-case behavior of AC-4 while improving on the average-case behavior of AC-3 [Bessiere and Cordier, 1993]. The new algorithm schema, AC-Inference, owes something to all these predecessors, but permits use of inferred support; AC-7 is most closely related to AC-6. This paper merges and extends previous independent work by the authors [Bessiere and Regin, 1994; 1995; Freuder, 1995].

The potential redundancy in processing of bidirec­ tional support has been recognized before. When AC-3 removes a value from the domain of variable X because it has no support in variable Y, it realizes that this can­ not cause a value of Y to become bereft of support at X. DEEB [Gaschnig, 1978] uses a "revise-both" procedure that more directly anticipates AC-7. After the values for X are checked for support at Y, values for Y are im­ mediately checked for support at X, but only those Y values that have not just provided support for X values are checked. Gaschnig points out that this avoids un­ necessary checks performed by AC-3 the first time the domains of X and Y are checked against each other; but he incorrectly, it seems to us, concludes that DEEB also avoids all the checks that AC-3 avoids by utilizing bidirectionality.

Neither algorithm, however, has any long term mem­ ory of inferences based on bidirectionality. For exam­ ple, suppose that the first value, x1 , and last value, x100 , among a hundred values for X are found to be supported by a value y for Y. If later x1 is deleted during the con­ straint propagation process, neither AC-3 nor DEEB will remember that y still is supported by x 100 . In fact they may need to look at the other 98 values for X before "rediscovering" that y is supported by x 100 . More gen­ erally, both AC-3and DEEB are "arc revision" oriented, while AC-7 is "support maintenance" oriented, in the spirit of AC-6. As a result, AC-7 will have the same sort of constraint check advantage over AC-3 that has been demonstrated for AC-6, plus the additional advantage provided by inferences based on bidirectionality.

2 Inferring Support

2.1 Principle

We illustrate the principle of inferring support with a simple coloring problem example. Consider a trivial one for illustration purposes. The problem is to assign a color, a (aquamarine), b (blue) or c (coral), to each of two countries, X and Y, such that X and Y have differ­ ent colors. As a CSP, the countries are the variables, the colors the values. The constraint between the two vari­ ables specifies that the two countries cannot have the same color (i.e. it is a not-equal constraint).

A value, (i, a), is arc inconsistent if there is a vari­ able for which there is no value that supports (i, a). We achieve arc consistency by removing all arc inconsistent values-or in this simple coloring problem by verifying that there are no arc inconsistent values. In general, removing one value may make another value arc incon­ sistent, so we say that achieving arc consistency can in­ volve a constraint propagation process. However, in this simple example we do not have to worry about that.

The AC-4 arc consistency algorithm operates by first checking for all possible support. It stores summary in­ formation in support counters, and is later able to im­ plement constraint propagation efficiently when propa­ gation is required, by updating the counters rather than by performing further constraint checks. However, its brute force initial processing is costly; it performs all pos­ sible constraint checks twice (this total can be reduced when values are deleted during initial processing). Eigh­ teen constraint checks are required for this little problem. These are shown in Figure 1a. The values for country X are on the left, for country Y on the right. An arrow from a value u for X to a value v for Y indicates that a check of the consistency of (X, u) with (Y, v), (denoted by Rxy(u, v)), has been computed while seeking sup­ port for (X, u). The double ended arrows indicate that redundant checks were made, while seeking support for both (X, u) and (Y, v). A solid arrow indicates that the check established consistency; a dashed arrow indicates that the check established inconsistency.

AC-3 seeks only to establish that each value has a supporting value (at every other variable). This only requires 8 constraint checks here (Figure lb), but some of them are redundant. In general, AC-3 propagation can involve additional redundant checking, but this does not enter in here. AC-6 can improve on AC-3 by avoid­ ing some redundant checking during propagation. If the support it finds initially is deleted, it proceeds on from that point to look for another support; it does not need to "start over" as AC-3 does. However, in this simple example, AC-6 has no opportunity to exhibit this addi­ tional intelligence. It too requires 8 constraint checks.

AC-3 may check pairs once, twice, or more than twice. AC-4 checks each pair at most twice. AC-6 was said to be optimal in the sense that it only made necessary checks. (The actual number of checks it makes is still subject to processing order effects.) However, support inference based on the bidirectionality of support can reduce constraint checks further. AC-6 (AC-3 and AC-4 as well) checks, for example, that (X, a) is supported by (Y, b), and then separately checks that (Y, b) is supported by (X, a). These algorithms can not say: "oh, I already know (Y, b) is supported; I just found that out while looking for support for (X, a)".

The AC-7 algorithm that we propose here can, in ef­ fect, say this. After it checks (X, a) against (Y, b) and finds that the latter supports the former, it infers that the former also supports the latter. This inference is based upon the simple metaknowledge that support is bidirectional. Utilizing such inferences, AC-7 only re­ quires 5 constraint checks to establish arc consistency. This is shown in Figure lc. Large barbed arrowheads are used to indicate inferences. The double-ended ar­ rows here, with a barb on one end, indicate a constraint check in one direction followed by a constraint inference in the other. Notice that negative support information can also be inferred: after performing a constraint check to determine that (Y, a) does not support (X, a), we can infer that (X, a) does not support (Y, a).

Moreover, AC-7 is but one instance of the general prin­ cipal of using constraint metaknowledge to infer or avoid constraint checks. We will illustrate this point with a couple of further examples. Suppose we have further metaknowledge of these constraints. Suppose we know that they are also irreftexive: Rxy(v,v) does not hold for any v. Then the number of checks can be reduced to 4. Irreftexivity allows us to immediately infer that (X, a) is inconsistent with (Y, a), making it unnecessary to check this (Figure ld). Suppose we know that the con­ straints are commutative: Rxy(u, v) = Rxy(v, u). This permits us to reduce the number of constraint checks to 3. For example, after checking Rxy(a, b) we can infer Rxy(b, a). See Figure le. If we know they are irreftexive and commutative, we are down to two checks, Figure lf.

Finally, suppose we know that the constraints are in­ equality constraints. What does it mean to know that they are inequality constraints? Well one thing it could mean is that we have an inference rule that says sim­ ply: if the constraints are inequality constraints, and the domains contain more than one element, forget arc consistency processing-the problem is already arc con­ sistent. This reduces the processing to zero constraint checks. Less dramatically, but potentially of considerable significance, we may have a problem in which some of the constraints appear repeatedly involving different variables. A consistency check involving one of these "repeated" constraints can permit us to infer support in­ formation for all these variables (to the extent to which they share common domains).

2.2 Schema

The key to the inference schema, as it is to AC-3, AC-4 and AC-6, is maintaining appropriate information. AC-3 determines which values need to be rechecked to see if they are still supported. AC-4 computes a total support count initially and then updates it as values are deleted. If AC-Inference needs to find support for value (i, a) at variable j, it looks through an ordered list of j values for a single supporting value, b. If b is deleted, AC-Inference looks for another supporting value later in the list.

The schema data structures are something of a hybrid of AC-4 and AC-6. Conceptually, for each value, a, for each variable, i, and each other variable j, which shares a constraint with i, AC-Inference maintains a support set of values from Dj that support (i, a), and the unchecked set of values from Dj that have not yet been checked to see if they support (i, a). (Values that have been checked and found not to support (i, a) appear in neither set.)

Maintaining these sets enables the schema to remem­ ber inferred constraint check information. Positive re­ sults are remembered by adding to the support sets. Negative results are remembered by deleting from the unchecked sets. Like AC-6 we only have to work through the unchecked sets once; unlike AC-6 we can avoid some of those values via inference.

The support data structures of AC-4 accept additional support during the initialization phase and can be mod­ ified to reflect deletion of support. For the schema, sup­ port can be both added and deleted throughout the pro­ cessing. AC-6 proceeds through the variable domains as necessary looking for support, ignoring deleted values. The schema does the same, ignoring also values whose support status has already been inferred. The number of supporting and unchecked values can be maintained to facilitate deletion decisions.

The schema can be expressed as a processor for two streams.

AC-Inference Schema:

Initialize the seek-support stream

Establish the initial support and unchecked sets, using any initial inferences

Repeat until done:

If process-deletion stream is not empty, process its first element

else if seek-support stream is not empty, process its first element

else done

The seek-support stream contains value-variable pairs. If a is a value for a variable i and the variable j shares a constraint with i, [(i, a), j] will appear on the initial seek­ support stream. Processing an element of this stream in­ volves looking for support for the value in the unchecked set of the variable. After each constraint check a set of inferences is made, based on the outcome. The specific set of inferences chosen instantiates the schema. The process-deletion stream consists of values whose support and unchecked sets at some variable are both empty. Processing a deletion involves removing it, at least con­ ceptually, from the domain of values for its variable, and the support and unchecked sets in which it appears.

When both the support and unchecked sets for a value with respect to a variable become empty, that value en­ ters the process-deletion stream. This can happen either as the result of seeking support or processing deletion. When only the support set for a value with respect to a variable becomes empty, that value enters the seek­ support stream. This can happen as the result of pro­ cessing a deletion. Notice that we respond to deletions immediately. Furthermore we recommend implementing the seek-support stream as a stack, so that the effects of deletions will propagate immediately. We believe this to be an improvement on the "two-pass" organization of AC-4 and AC-6.

3 AC-7

AC-7 refines the AC-Inference schema, while restricting inferences to those based on bidirectionality. Since bidi­ rectionality is a general property of constraints, AC-7 is a general purpose arc consistency algorithm. Also by restricted our inferences to bidirectionality we are able to maintain a space complexity of the same order as AC-6, namely O(ed), for a problem with e constraints and maximum domain size d. AC-Inference (and AC-4) space complexity is quadratic in d. In some applica­ tions, the size of the problem (number of variables, size of the domains, number of constraints) is so high that it is impossible to store in memory all the support sets and unchecked sets needed by AC-Inference. Swapping slows down running time. AC-7 avoids the space requirements of AC-Inference by using an AC-6-like data structure to avoid the constraint checks that would be inferred by AC-Inference.

A C-7 has the following desirable properties. A C-7:

1. never checks Rij (a, b) if there exists b' still in D i such that Rij (a, b') has already been successfully checked.
2. never checks Rij (a, b) if there exists b' still in D j such that Rji ( b', a) has already been successfully checked.
3. never checks Rij (a, b) if:
4. it has already been checked

or b) Rji(b, a) has been checked.

1. has O(ed) space complexity.

AC-3 lacks properties (1), (2), (3a), and (3b). AC-4 lacks (1), (2), (3b), and (4). AC-6 lacks (2), and (3b), the properties resulting from bidirectionality.

3.1 Data structure

Every time a constraint check Rji(b, a) is performed, AC-7 needs to store this information to avoid future Rij (a, b) or Rij (a, b') checks forbidden by properties (3b) and (2). This storage must be done in a careful way to avoid falling into the trap of an O(ed 2 ) space complex­ ity. AC-7 does this by adding two refinements to the data structures of AC-6.

AC-6 assigns an ordering of the values in every Di, checks one support (the first one) for each value (i, a) on each constraint Rij to prove that (i, a) is currently viable. When (j, b) is found as the smallest support of (i,a) on Rij, (i,a) is added to S[j,b], the list of values currently having (j, b) as smallest support. If (j, b) is removed from Dj then AC-6 looks for the next support in Di for each value (i, a) in S[j, b]. In AC-7, S[i, a] sets are split into S[(i,j), a] sets, to support property (2): each value (i, a) has a set of values supported by it per constraint instead of one for all the constraints. bE S[(i, j), a] implies (i, a) is known as supporting (j, b) on Rji, then (i, a) is compatible with (j, b). Hence, an Rij(a,b) is checked if and only if S[(i,j),a] = 0, other­ wise we know (i, a) has a support on Rij without any new constraint check. Also, arrays inf-support are added to support property (3b) for negative constraint checks and property (3a) 1 : inf-support[(i, j), a] represents the small­ est value in Dj which may be compatible with (i, a).

In more detail the data structure of AC-7:

• A table M of Booleans keeps track of which values of the initial domain are in the current domain or not (M[i, a]=true <=> a E Di). In this table, each initial Di is considered as the integer range LIDil · We use the following constant time functions and procedures to handle Di lists. last(Di) returns the greatest value in Di if Di =f. 0, else returns 0. If a E Di \last(D;), next( a, D;) returns the smallest value in Di greater than a. remove( a, Di) removes the value a from Di. remove( a, Di) can be extended to stop the arc consistency algorithm if a was the only remaining value in D;. The CSP, indeed, has no solution.
• For all a in Di, S[(i,j), a] contains all values bin Dj for which (i, a) is assigned as its current support. The current support is not necessary the smallest one, as opposed to AC-6.
• Arrays inf-support are updated by AC-7 to ensure that every bin Dj compatible with (i,a) is greater than or equal to inf-support[(i,j),a].
• DeletionStream and SeekSupportStream have the same behavior as in AC-Inference. Handling the SeekSupportStream as a stack seems to be an ef­ ficient heuristic because it propagates the conse­ quences of deletions as soon as they appear, and then discovers empty domains earlier.

3.2 Algorithm

The algorithm AC-7 (see Fig. 2), has the same frame­ work as AC-Inference. There are two main operations: processing the deletion of a value, and seeking a new sup­ port for a value. AC-7 processes the deletion of a value (j, b) by adding in the SeekSupportStream all the value­ variable pairs [(i, a),j] such that (i, a) was supported by

1 Property (3a) held in AC-6 without inf-support arrays because we knew that ( i, a) was always the smallest support for values in S[i,a]. In AC-7 we lose this strong property.

(j, b) (i.e. values (i, a) that were in the S[(j, i), b] sets). The search on R;i for a new support for a value (i, a) is only done if S[(i,j),a] does not contain values in Di; otherwise, this search is useless: (i, a) has inferable sup­ ports on R;j (since values supported by (i, a) are sup­ ports for ( i, a)). If the search of support is done for a value (i, a) on R;j and a value c is found, a is added to S[(j,i),c] since cis now the current support of (i,a). inf-support[(i, j), a] records cas the smallest value in Di supporting (i, a) on R;j since the search follows the order of D i. During the whole algorithm, every time a value is found without support on a constraint, it is removed from D and put in the DeletionStream.

DeletionStream ~ 0; SeekSupportStream ~ 0; for each (i, a) E D do M(i, a] ~ true; for each ( i, j) I R;j exists do for each a E D; do S((i,j), a]~ 0; inf-support((i,j),a] ~ 1 I* first value of Dj *I; put ((i, a), j] in SeekSupportStream; repeat until done if DeletionStream =I 0 then pick (j, b) from DeletionStream; for each i I Rj; exists do for each a E S((j, i), b] do delete a from S((j, i), b]; put ((i,a),j] in SeekSupportStream; else if SeekSupportStream =10 then pick ((i, a),j] from SeekSupportStream; if M(i, a] then else done if SeeklnferableSupport( ( i, j), a, c) then put a in S((j, i), c] else c ~ in/-support( ( i, j), a]; if SeekNextSupport((i,j), a, c) then put a in S((j, i), c]; inf-support((i, j), a] ~ c else remove( a, D;); M(i, a] ~ false; put (i, a) in DeletionStream;

The function SeekNextSupport (Fig. 3), which looks for the smallest value in Dj not smaller than band sup­ porting (i, a) on R;j, is the same as in AC-6 except the addition of the test of line 3 to avoid checking R;j(a, b) when Rj;(b,a) has already been checked as false (i.e. when we know that (j, b) has no support in D; until a value greater than a).

Another function, SeeklnferableSupport (Fig. 3), is used in AC-7 to check whether a value (i, a) has inferable supports on R;j or not (i.e. whether S[(i, j), a] contains values in Di or not). Every time SeeklnferableSupport unsuccessfully checks if a value bin S[(i,j),a] is in Dj, b is deleted from S[(i,j),a] to avoid checking it again in the following.

3.3 Analysis

We first show that AC-7 has all of the desirable proper­ ties enumerated earlier.

By the same principle as with AC-6, properties (1)

and (3a) hold. Indeed, we stop looking for supports for a value (i, a) on R;j as soon as we find the first support, and an R;i (a, b) cannot be checked twice since we start looking for a new support for (i, a) on R;j where we stopped the previous time.

Every time a constraint check Rji ( b, a) is successfully performed (when looking for a support for (j, b)), AC-7 records bin S[(i,j),a]. Since AC-7 only looks for a sup­ port for (i,a) on R;i if S[(i,j),a] n Di = 0, we are sure that R;j (a, b) is only checked when none of the previ­ ously done constraint checks on Rj; can prove that ( i, a) has a support in Dj. Property (2) holds.

Next, we have to prove that when we check R;j(a,b), Rj;(b,a) has never been checked before. If Rj;(b,a) has already been successfully checked, b must be in S[(i,j), a] or out of D, and R;j(a, b) cannot be checked. If Rj;(b,a) has been checked as false, that means that we have looked for a support for (j, b) in D; and that (i, a) was not a support. So, if bE Dj, inf-support[(j,i),b] is greater than a, and line 3 of function SeekNextSupport avoids checking R;i(a, b). Property (3b) holds.

The worst-case space complexity of AC-6 was O(ed) because of the size of S[j, b] sets. In AC-7, S[j, b] sets of AC-6 are split into S[(j, i), b] sets. This does not in­ crease their total size: each arc-value pair [(i,j),a] has at most one current support (j, b) (i.e. a belonging to S[(j, i), b]). Hence, the total size of the S[(j, i), b] sets is bounded above by O(ed). We have to add arrays inf­ support, which take a 2ed space. Thus, the total space complexity of AC-7 remains O(ed).

Note that AC-7 can do much more than avoid the com­ putation of inverse checks that establish whether (i, a) supports (j, b) after establishing whether (j, b) supports (i,a). Inferring one support may permit us to avoid a number of additional constraint checks.

We will demonstrate the savings that are possible for AC-7 with a simple example. Figure 4 shows the mi­ crostructure of the example in the form of a consistency graph, where each consistent pair of values is joined by an edge. The problem involves just two variables, assuming the variables are ordered from top to bottom. In this example the number of checks for AC-7 is 21; for AC-3 or AC-6, 48, for AC-4, 64.

This example can be generalized from domain sizes of 8 to domain sizes of d, where O(d 2 ) checks are saved. Observe that it is constructed so that d/2 of the values in the second domain (y2 to y5 ) must be checked (and fail) against from d/2 to d- 1 of the values in the first domain with AC-3 or AC-6, while AC-7 avoids these checks entirely. Thus we have established the following:

Theorem 1 AC-7 can save O(d 2 ) non-inverse con­ straint checks for domain size d.

Notice that we have established this theorem without even considering constraint propagation, where further savings may be realized. Bear in mind that inferring non-support and utilizing it immediately can justify the deletion of values. Early deletions of values can lead to further savings, as we no longer have to seek support for these deleted values, or consider them as possible supports for other values. It may even lead to early discovery of unsolvability. We would expect AC-7 to show to better advantage on more tightly constrained problems, where one has to look harder to find support, and thus can benefit more when inferences preclude the need to look for support.

We would expect AC-7 to show to best advantage on problems with structures such as those above, that can especially benefit from the undirected constraint infer­ ences. Changing the order in which values are considered can increase (or reduce) the advantage of AC-7, but since these advantages are tied to the structure of the consis­ tency graph, and since determining consistency graph structure involves performing the very constraint checks we are trying to avoid, it is difficult to argue strongly for or against AC-7 based on such ordering considerations. However, in specific cases, we might be able to utilize metaknowledge of the consistency graph structure for effective value-ordering heuristics.

We have been focusing on constraint checks, which are a standard measure of CSP algorithm performance. Of course, constraint checks alone do not tell the whole story. However, if we either assume a large enough cost per constraint check, or demonstrate a large enough sav­ ings in the number of constraint checks, the constraint check count will dominate overhead concerns. AC-7 can even permit us to cope with some situations where some constraint checks cannot be computed at all.

4 Experimental results

We tested AC-Inference and AC-7 on two real-world problems. (Since AC-Inference is an algorithm that takes advantage of constraint semantics, we would not expect it to do best on random problems.) The first is the Radio Link Frequency Assignment problem (RLFAP). We took problems from a set that stem from real instances, which is available in a CSP benchmarks archive maintained by Michael Jampel (ftp.cs.city.ac.uk:jpubjconstraintsjcsp­ benchmarks). In this problem, all the constraints are commutative and irreflexive since for every pair of vari­ ables Xi and X1, only two types of constraints are pos­ sible: I Xi- Xj I > k, or I Xi- X1 I = k, k being a positive number. The number of values fork are limited, so that many constraints in the network are repeated. The sec­ ond is a RNA problem in molecular biology. The goal is to forecast the structure of RNA molecules given these­ quence of nucleotides. The CSPs involved are exception­ ally large: 70-1542 variables, 40-550 values per domain, and a complete graph of loose constraints which are ir­ reflexive. The task is to achieve arc consistency alone. We also tested on the Zebra problem, a common CSP benchmark (also available in the benchmarks archive) .

We compared several versions of the MAC algorithm [Sabin and Freuder, 1994] on RLFAP and Zebra. MAC is a backtrack search algorithm where arc consistency is dynamically maintained as search choices are made. The versions of MAC we tested differ in the type of arc consistency algorithm they use. MAC4 is based on AC-4 2 , MAC6 on AC-6 (two-pass organization), MAC6+heuristic on an AC-6 version implemented with our heuristic (processing deletions first) , MA C7 on AC-7, MAC-I on AC-Inference when reflexivity, commutativity and irreflexivity are used, and finally, MAC-l+repeated, based on AC-Inference, when, in addition, repeated con­ straints are taken into account 3 . On the RNA problem, we compared AC-4, AC-6, AC-7 and AC-Inference. All the results are given in Table 1.

Experimental results give us some interesting informa­ tion. First, the number of constraint checks is strongly correlated with cpu time, even on this kind of problem where constraint checks are cheap to compute. This means that, generally, the benefit of inferences not only offsets, but also overcomes their cost. (Otherwise, "#ccks" would have decreased from MAC4 to MAC­ l+repeated while "time" would not). The very good run­ ning times of MAC-l+repeated confirm the advantage of using the most metaknowledge we can. Second, the re­ sults of MAC6 and MAC6+heuristic show the effective­ ness of our heuristic (processing deletions first) on prob­ lems with a large propagation at the first arc consistency call 4 (e.g. RLFAP #5-12046 values deleted, RLFAP #8- arc inconsistent, as opposed to RLFAP #3- 0 val­ ues deleted, RLFAP #11- 0 values deleted). Finally, the RNA problem shows the consequences of tackling space complexity: AC-4 and AC-Inference could not process sequences larger than "HIV1" (124 variables, an average of 47 values per domain, 7626 constraints), while AC-6 and AC-7 could process "rnasePcoli" (377 variables) . On the RNA problem we can also remark on the small dif­ ferences in performance between AC-6, AC-7 and AC­ Inference, explained by the looseness of the constraints (finding a support is easy) .

2 The number of constraint checks for MAC4 is the same as the number of constraint checks for the first AC-4 call, since all support information is then in the support sets.

3 MAC3 was not used because it has a behavior really worse than the other algorithms, except on very easy in­ stances where it can outperform MAC4.

4 because MAC6 contains the expensive initialization phase of AC-6 (which is only performed at the first call) , while MAC6+hev.ristic already benefits from the good be­ havior of the heuristic.

5 Conclusion

Metaknowledge about constraints can be used to infer, rather than compute, support information, and to both infer and avoid constraint checks. A variety of basic properties of constraints can be exploited in this way. The AC-Inference schema permits exploitation of infer­ ences in establishing arc consistency. AC-7 is a refine­ ment of that schema that exploits only the bidirection­ ality of support; thus is a fully general arc consistency algorithm. AC-7 can exhibit significant savings over pre­ vious general arc consistency algorithms. AC-Inference may prove especially useful when constraints have strong structural properties , when some constraints appear re­ peatedly or when support is costly to compute.

Acknowledgements

This material is based in part on work supported by the National Science Foundation under Grant No. IRI9207633. We thank Thomas Schiex and the French Centre d'Electronique de l'Armement for making RLFAP available, Christine Gaspin for providing the RNA problem and Alan Mackworth for a helpful discussion.