Arc Consistency for General Constraint Networks: Preliminary Results

1 Introduction

1.1 Overview

Constraint satisfaction problems (CSPs) occur widely in artificial intelligence. They are used more and more in real-life applications, such as resource allocation, crew scheduling, time tabling, frequency allocation, car se­ quencing, etc. The CSP involves finding a solution in a constraint network, i.e. finding values for problem vari­ ables subject to constraints.

The general task of solving a CSP being NP-hard, many researchers have concentrated on improving the efficiency of finding a solution in a constraint network. Particularly, arc consistency caught many researchers' attention, involving the discovery of a large number of

Jean-Charles Regin

ILOG S.A.

9 rue de Verdun 94253 Gentilly Cedex, France

Email: regin<Oilog. fr

algorithms [Mackworth, 1977a], [Mohr and Henderson, 1986], [Bessiere, 1994], [Bessiere et al. , 1995]. And, re­ cently, the value of these studies on arc consistency in­ creased since it has been shown that maintaining arc consistency during search is definitely a worthwhile ap­ proach when solving large and hard problems [Sabin and Freuder, 1994], [Bessiere et al., 1995], [Bessiere and Re­ gin, 1996], [Grant and Smith, 1996].

However, results about CSP solving and about arc consistency are almost always limited to binary con­ straint networks, justified by the fact that any non­ binary constraint network can be translated into an equivalent binary one with additional variables [Rossi et al. , 1990], [Dechter, 1990]. But, in practical cases, it is often inconceivable to translate a non-binary con­ straint into an equivalent set of binary ones with the technique cited above because of the underlying compu­ tational and memory cost. When a constraint is repre­ sentable [Montanari, 1g74]) , it is sometimes possible to replace it by a set of binary constraints without introduc­ ing new variables and without generating explicitly the set of allowed tuples of each binary constraint. For ex­ ample, a constraint enforcing that the three variables x1, x2 , and x3 must all take different values can equivalently be replaced by the three binary constraints x1 =fi x2, x1 =fi x3 , and X2 =fi X3. But, as it has been shown in [Regin, 1994], non-binary constraints lose a part of their semantics when encoded into a set of binary ones in this way. This leads, for example, to less pruning for arc consistency algorithms handling them.

Hence, if we no longer want to consider the CSP as an academic problem we must be able to deal with any kind of constraints, and so, with non-binary constraints, as widely required in real-world constraint solvers.

1.2 Previous work

In the constraint satisfaction community, the number of works involving non-binary constraint networks is rather small. For the particular case of arc consistency, we know two algorithms capable of achieving it. Mackworth [Mackworth, 1977b] proposed the algorithm CN, which is a kind of generalization of AC-3 to non-binary con­ straints. As AC-3, that algorithm has a bad worst-case time complexity (O(er 2 dr+l ), withe the number of con­ straints in the network, r the maximal arity of the con­ straints, and d the size of the largest domain). Mohr and Massini [Mohr and Masini, 1988] proposed GAC4. It is based on the same idea as AC-4 (computing the number of supports for each value in each domain and removing those with this number equal to zero). Thus, it gets rid of the huge worst-case time complexity of CN (GAC4 is in O(edr)), but has the same drawbacks as AC-4: space complexity (because of the lists of supported values), and average time complexity. The respective drawbacks of CN and GAC4 are even more important than on their bi­ nary versions, so that CN can only be applied on ternary constraints and very small domains, and GAC4 on very tight constraints, where the number of allowed tuples of values is very small.

Finally, we can point out the work of van Beek and Dechter [van Beek and Dechter, 1995], who proposed another definition for arc consistency on non-binary con­ straint networks, namely relational arc consistency. This definition is much stronger than the classical one since for each com;traint it requires global consistency on the underlying subnetwork (i.e. the network involving the variables of the given constraint, and all the "smaller" constraints defined on some of these variables).

1.3 Our purpose

Our general aim is to propose a new schema in order to perform arc consistency on any real world constraint network with a reasonably low time and space complex­ ity. In industrial applications, a constraint can be given in many different forms: by the set of allowed tuples in extension (generally when the constraint is very tight), by the set of forbidden tuples in extension (when the constraint is very loose), by a conjunctive constraint, by an arithmetic relation, or by any predicate for which no particular semantics is known (data base query, user's context-dependent constraint, etc.). Thus, a suitable arc consistency algorithm should be able to efficiently handle any of these constraints.

The particular aim of this paper is to present the first steps of our work. First, we will present our general schema for arc consistency on non-binary constraint net­ works. This schema is based on the AC-7 schema given in [Bessiere et al., 1995]. It makes use of the "current support" idea, and of "multidirectionality" (the gener­ alization of bidirectionality to non-binary constraints) in order to save as many constraint checks as possible. Second, we will instantiate this schema with some of the most frequently occurring forms of constraint represen­ tations.

Constraints defined by a predicate for which no partieular semantics is known are one of the most important forms that have to be handled. Indeed, if we except the predicates for which specific algorithms are known (arithmetic relations [Van Hentenryck et al., 1992], car­ dinality constraints [Regin, 1996], etc.), the only avail­ able algorithms for non-binary constraints are CN and GAC4. GAC4 deals only with constraints given in exten­ sion, and then is not capable of handling a predicate, even if, theoretically, it is always possible to build the whole set of allowed tuples by checking all the combi­ nations of values for the variables involved in the con­ straint. It would be impracticable, at least because of space requirements. Moreover, asking the value of a predicate for a particular combination of values (a con­ straint check) can be very costly in practice, when the answer is contained in a database, or requires heavy com­ putation. This definitively eliminates CN, with its huge time complexity, doing and doing again many times the same constraint checks. Therefore, we will propose an instantiation of the schema that will efficiently handle predicates, minimizing the number of constraint checks. However, this schema is certainly not competitive on predicates for which a specific algorithm is available.

Afterwards, we will instantiate the schema for con­ straints defined by a set of forbidden tuples. This kind of representation is of practical interest when constraints are very loose.

Finally, we will show that the schema can also deal with constraints defined by the list of allowed tuples given in extension. It leads to an improvement on GAC4, which was already written for that kind of constraint.

2 Preliminaries

Constraint network. A finite constraint network P is defined as a set of n variables X = { x1, ... , Xn}, a set of current domains V = {D(x1 ), ... ,D(xn)} where D(x;) is the finite set of possible values for variable x;, and a set C of constraints between variables. We intro­ duce the particular notation Vo = {Do(xl), ... , Do(xn)} to represent the set of initial domains of P. Indeed, we consider that any constraint network P can be associated with an initial domain V0 (containing V), on which con­ straint definitions were stated. A total ordering <d can be defined on D(x;), Vx; EX, without loss of generality. Constraints. A constraint C on the ordered set of variables X (C) = (x;, . . . , x;J is a subset of the Cartesian product Do(x;,) x · · · x D0 (x;J that speci­ fies the allowed combinations of values for the variables x;, x ... x x;r. An element of D0 (x; 1 ) x · · · x D0 (x;J is called a tuple on X (C). Two tuples T and r' on X (C) can be ordered by the natural lexicographic order -<to in which T -<to T 1 iff 3kjr[l..k- 1] = r'[l..k- 1] and r(k] <d r'[k] (r(l..k] being the prefix of size k of T, and r(k] the kth value of r). The tuples of D0 (xiJ x · · · x D0 (xiJ not allowed by Care called the forbidden tuples of C. Verifying whether a given tuple T is allowed by C or not is called a constraint check. IX(C)I is the arity of C.

A constraint C involving the subset of variables X (C) = (xip .. . , xiJ can be defined by the set of al­ lowed tuples (resp. the set of forbidden tuples) given in extension when the constraint is tight (resp. is loose) , or by an arithmetic relation. More generally, it can be represented by any Boolean function f c defined on Do(Xi 1 ) x · · · x Do(xd.

Solutions. A solution of a constraint network is an instantiation of the variables such that all the constraints are satisfied.

Notation. A value a for a variable x is often denoted by (x, a). var(C, i) represents the ith variable of X(C), while index( C, x) is the position of variable x in X (C).

Arc consistency. Let P = (X, V,C) be a constraint network, C a constraint in C.

A tuple T of X(C) is valid if V(x , a) E T, a E D(x) ; otherwise, it is rejected.

A value a E D(x) is consistent with C iff x fl. X(C), or 3T allowed by C, such that a = T[index(C, x)] and T is valid. (Tis then called a support for (x,a) on C.)

C is arc consistent iff Vxi E X(C), D(xi) =f. 0 and Va E D(xi) , a is consistent with C.

P is arc consistent iff all the constraints of C are arc consistent.

We achieve arc consistency in P by removing every value not consistent with at least one constraint in C.

3 A general schema for arc consistency

As we pointed out in Section 1, our general aim is, on the one hand, to provide a schema sufficiently general to be instantiated with any kind of constraint. On the other hand, this schema must be powerful enough to avoid as many constraint checks as possible when achieving arc consistency.

We did not choose an AC-3like or an AC-4like schema for efficiency reasons. To be reasonably efficient, the schema has to be based on AC-6 or AC-7. They are both based on the search of a single support for each value, the worst-case time complexity being optimal in both algorithms. The difference between them is whether or not they deal with bidirectionality [Bessiere et al., 1995].

In a non-binary constraint network, any constraint is multidirectional, as any constraint is bidirectional in a binary constraint network. Multidirectionality, indeed, is the fact that for any constraint C, a tuple T on X (C) is a support for the value T[index(C,x)] (x being a vari­ able involved in C) iff Vy E X(C) , r is a support for r[index(C, y)]. We say that an algorithm "deals with" multidirectionality iff it never checks whether a tuple is a support for a value when it has already been checked for another value, and never looks for a support for a value on a constraint C when a tuple supporting this value has already been checked.

And, dealing with multidirectionality appears to be promising on non-binary constraints. A tuple T, indeed, allowed by a constraint C, can support IX(C)I values. Thus the possible savings are much more important than on binary constraints. AC-7 could save d 2 constraint checks thanks to bidirectionality, where dis the domain size of the variables involved (see [Bessiere et al., 1995]), while dr constraint checks can be saved thanks to mul­ tidirectionality on an r-ary constraint.

The framework we propose is then an AC-7 like schema in which search for support (function seekNextSupport) is instantiated differently depend­ ing on the type of the constraint involved. This schema (named GAC-schema) is able to handle any type of constraint, as soon as the corresponding func­ tion seekNextSupport is available. Before giving the seekNextSupport function associated with the types of constraints we will study in this paper (in the next section), let us describe the function propagation (see Alg. 1). The program including it must create and ini­ tialize the data structures (Sc,S, and lastc), and call propagation(C, x, a, deletionStream) for each constraint C involving x, each time a value (x, a) is removed from D(x), in order to propagate the consequences of this deletion.

Sc, S, and taste must be initialized in a way such that:

• Sc(x , a) contains all the allowed tuples r that are the current support for some value, and such that r[index(C, x)] =a.
• S(r) contains all values for which r is the current support.
• taste (y, b) is the last tuple returned by seekNextSupport as a support for (y, b) if seekNextSupport(C, y, b,-) has already been called; nil otherwise. taste(y, b) is perhaps no longer a support in C for (y, b) (if it is no longer valid and seekinferableSupport has found a new support for (y, b)). It is just here to give the point where seekNextSupport will have to restart the search for a support for (y, b) on C at the next call. There is an underlying ordering on the tuples, which is proper to seekNextSupport.

Property 1 VC E C, \:/allowed tuple T : S ( T) -:j:. 0 <* Vx E X(C), r E Se(x, r[index(C, x)]).

Property 2 Given any constraint C of arity r, the space complexity of the data structure of GAG-schema for Cis O(r 2 d).

Proof. Each· value has at most one support, then E IS(r)l :$ rd and there are at most rd tuples in mem­ ory. Each value is associated with one lasta, so the lasta data structure requires rd pointers. A tuple con­ tains r elements, thus the set of all tuples that support at least one value can be represented in O(r 2 d) . The number of elements that belong to Sa is bounded above by r 2 d by property 1 and because L: IS(r)l :$rd. Since an element of an Sa list corresponds to a pointer to a tuple, the space complexity of the data structures of GAC-schema for C is O(r 2 d). ·

Each time a value (x,a) is removed from D(x), we must propagate this deletion to each constraint C in­ volving x. So, for all the values (y, b) that were sup­ ported by a tuple containing a· in position index( C, x) , we must find another support (line 2). To take multi­ directionality into account, we first check (lines 3 and 4) if there exists a valid tuple containing (y, b) that is already the current support for another value (function seekinferableSupport, Alg. 2) . If not, the function seekNextSupport will look for another support for (y, b), starting the search from laste (y, b) (line 5). If a new sup­ port a is found for (y, b) on C, (y, b) is recorded as being currently supported by a (line 6), and for each value contained in a, we store the fact that a is the current support for some value (line 7); otherwise, (y, b) has to be removed (lines 8 to 9) .

4 The main types of constraint representations

In this section, we will present the instantiation of the schema in order to deal with three types of constraints.

Algorithm 2: function seekinferableSupport .

seekinferableSupport {in C: constraint ; in y: variable; in b: value): tuple while Sa (y,b) # 0 do l a+-- first(Sa (y,b)) ; if 3kja[k] rt D(var(C, k)) then remove a from Sa (y,b) ; else return a /* a is a support * / ; return nil ;

Constraints given by a predicate for which we do not know specific algorithms is the most important type. In­ deed, there does not exist any tool to process a predi­ cate in reasonable time and space. Afterwards, we will present a type of constraint which can be viewed as a special case of predicate constraints: constraints given by the set of forbidden tuples. Finally, we will give the seekNextSupport function capable of processing con­ straints given by the set of allowed tuples.

4.1 Predicates

When a constraint C is defined by a predicate for which no particular semantics is known, it is necessary to define an ordering on the tuples that will be followed when looking for a support for a value (y, b) on C. By means of the function nextTuple (Alg. 3), the lexicographic order -<to defined in Section 2 is used to examine the valid tuples on X(C). Given any tuple T on X(C), and any index k $ IX(C)I, nextTuple(C, y, b, r, k) will return the smallest valid tuple a greater than r w.r.t. -<to, such that the value of y in a is b, and such that the prefixes of size k of a and r are not equal. The second parameter returned by nextTuple is the smallest index k' on which a and r have different values.

When the function seekNextSupport (see Alg. 4) is called to search for a new support for (y, b) on C, we know from seekinferableSupport that there does not exist any tuple already checked that supports (y, b) on C . However, we have to take care to avoid checking a tuple r which has already been unsuccessfully checked for another value of another variable of X(C). We name candidate a valid tuple which has never been checked and thus, which could be a support for (y, b), as op-

Algorithm 3: function nextTuple

nextTuple (in C: constraint ; in y: variable; in b: value; in r : tuple; ink: index): (tuple, index) /* returns (a, k') where: · a is the smallest valid tuple such that a[index( C, y )] = b, r -<to a and a[l..k] # r[l..k] · k' is such that a[l..k' -1] = r[l..k' -1] and a[k'J # r[k'] otherwise returns (nil,- ) * /

Note that k' will always be less than or equal to k.

posed to the valid tuples that have already been checked not to be allowed by C (when we look for support for another value). Dealing with multidirectionality implies only checking the candidates. This can be done by means of the function seekCandidateTuple (see Alg. 5) .

seekCandidateTuple(C, y , b, a, k) returns the small­ est (w.r.t .-<lo) candidate greater than or equal to a , where a is valid and a[l..k- 1) has been verified to be a possible prefix for a candidate. For each index from k to IX(C)I, seekCandidateTuple verifies whether a is greater than lastc (var(C, k) , a[k]), (denoted by>.) (lines 2 to 4). If a is smaller than >., the search for a candidate has to jump forward: either to the smallest valid tuple following a with a prefix different from a[l..k) (if a and >. were diverging before k) (line 6) , or directly to the valid tuple following A (if a and A were diverging after k) (line 8). When we jump forward to the next valid tuple greater than a or A, some values before index k may have changed. Then, the value k goes back to the smallest index where the value of a has changed (lines 7 and 9) to keep the property of line 1. When k reaches IX(C)I + 1, a is a candidate and is returned.

The function seekNextSupport(C, y, b, T) returns the smallest tuple greater than T which is checked to be al­ lowed by C. From line 1 to line 2, seekNextSupport as­ signs to a the smallest valid tuple following T (depending on whether T is nil or not). Afterwards, a is assigned to the smallest candidate (line 3). The search for a sup­ port for (y , b) on C is done in lines 4 to 6: we check a and jump to the next candidate until f c (a) returns true (line 5).

A sketch of proof.

We will simply show here that seekCandidateTuple cannot miss any candidates when jumping forward in lines 6 and 8.

line 6: suppose there is a candidate a' between a and the tuple returned by nextTuple{C, y , b, a, k) . This means that a'[l..k] = a[l..k] ; otherwise a' would be the tuple returned by nextTU:ple. So, a' is smaller than A because of lines 4 and 5. a'[k] being equal to a[k], a' cannot be a candidate because A = lastc (var(C, k) , a[k]) (see the definition of last a ).

line 8: suppose there is a candidate a' between a and A. Then, a'[l..k] is equal to a[l..k] since a[l..k] = A[l..k] (lines 3 to 5). Once again that is impossible because A = lastc (var(C, k) , a[k]) . Finally, a' cannot be equal to A since A is no longer a valid tuple. (Otherwise seekinferableSupport would have found it to support (y, b) .) ·

4.2 Constraints given in extension

Negative constraints

In this case, the constraint C is given in extension by the set offorbidden tuples, denoted by T(C). Even without loss of generality, we can assume that the constraint is very loose. (Otherwise, the space in memory needed prohibits us from using that representation.) Then T(C) contains few elements with regard to the set of tuples on IX(C)I. So, if we use the previous method with the predicate !c(a) such that f c (a) ¢:?art T(C) , then only a few constraint checks will be needed to find a new support or to prove there is none, because almost all valid tuples are candidates.

Such a predicate f c (a) can be efficiently implemented by using a method like hashing [Sedgewick, 1990). Hash­ ing, indeed, permits us to find whether an element be­ longs to a set S, with an O(ISI) space complexity, and an average time complexity close to a constant.

Positive constraints

In this case, the set of allowed tuples, denoted by T(C), is explicitly given. Thus, for one constraint, the space

Algorithm 6: function seekNextSupport

seekNextSupport (in C: constraint; in y: variable; in b: value; in dummy): tuple while elt(y,b) f nil do l u +- Tuple(elt(y,b)); if isVa~id(u) then return u ; elt(y, b) +- next(elt(y, b)) ;

return nil ;

complexity will depend on the size of T(C) similarly to GAC4. So, at first glance, it seems that the space com­ plexity of GAC4 cannot be improved. But, in practice, we may have a problem in which some of the constraints appear many times involving different variables. For in­ stance, in configuration problems, a configurator has to choose the most appropriate components among a cata­ log of predefined components and arrange them accord­ ing to constraints that can be assembly rules, perfor­ mance, etc. Most of the constraints involved with the same kind of components are repeated and are given by their common set of allowed tuples.

For a constraint C, the representation of the data structures of GAC4 corresponds to a particular repre­ sentation of T(C). So, if two constraints are given by T(C) , then GAC4 needs two distinct data structures, each with a O(IT(C)I) space complexity. Hence, for p repeated constraints the space complexity of GAC4 will be O(p · IT(C)I) . The algorithm we presented only re­ quires an explicit representation of S and Sc lists, and lastc pointers, for each constraint. This leads to a O(r 2 d) space complexity per constraint, r being the ar­ ity of the constraint involved (see Property 2). If the representation of T(C) can be shared by p repeated constraints, then the global space complexity will be O(IT(C)I + p.r 2 d) , and a factor p will be gained with regard to GAC4.

Such an algorithm can be defined by representing the common set T(C) as GAC4 does for one constraint and by using for each repeated constraint and each value (y, b) a pointer that indicates the last element reached in T(C). We will denote it by elt(y, b) . The algorithm does no longer compute the tuples and test them; it only looks for a support directly in T(C). The new algorithm is given by the function seekNextSupport (Alg. 6) which replaces the previous one. The function next(elt(y, b)) gives the next tuple in T(C) containing b for variable y.

5 Space and time analysis

Let C be a constraint of arity r with a tightness t (pro­ portion of forbidden tuples), and assume that all do­ mains have a size· d. Then, if a pointer is represented by 4 bytes, a good estimation of the memory required is:

• 16r · !{tuples on X(C) allowed by C}l 16rdr(l- t) Bytes for GAC4
• 24r 2 d Bytes for the GAC-schema, according to prop­ erty 2 ( C being a predicate 1 )

The table below gives some results about the space requirements of GAC4 and the GAC-schema. The sizes are given in Megabytes. Only the configurations associ­ ated with bold numbers can be used in practice. ("-" means that more than 256 Mb are needed.) Bear in mind that these space requirements are given for only one constraint.

Finally, to be exhaustive on complexities, we report the worst-case time complexities of the different versions of the GAC-schema presented in this paper. Let C be a constraint of arity r . If C is a predicate, the GAC-schema has a time complexity bounded above by O(dr). This is a gain of r 2 d with respect to the O(r 2 dr+l) of CN. If C is a negative constraint, the complexity remains very close to O(dr) (see subsection 4.2). If C is a pos­ itive constraint, the worst-case time complexity of the GAC-schema is O(IT(C)I). This is the same as the one of GAC4.

6 A cryptogram as an example

In this section we briefly present a very small example (a cryptogram) to show some of the advantages of deal­ ing with non-binary predicates. (This example is imple­ mented in ILOG Solver 4.0, in which the GAC-schema has been inserted.) For a complete presentation of the example, see [ILOG, 1997].

The cryptogram is given in Fig. 1. The problem is to find a one to one mapping from letters {A, B, D, E, G, L, N, 0, R, T} to {0 .. 9} in such a way that the addi­ tion obtained by replacing each letter by its associ­ ated value is consistent. It is possible to solve this problem without the GAC-schema, by encoding it (for instance) as the following constraint network: a vari­ able for each letter; a domain containing the num­ bers 0 .. 9 for each variable; and two non-binary con­ straints for which efficient specific algorithms are known, "100, OOOD + 10,0000 + 1, OOON + 100A + 10L + D +

1 For constraints given in extension we should add the size of the constraint representation (see subsection 4.2) .

100, OOOG + 10, OOOE + 1, OOOR + lOOA + lOL + D 100, OOOR + 10,0000 + 1, OOOB + lOOE +lOR+ T", and "all-different( A, B, D, E, G, L, N, 0, R, T)". However, with this representation, some of the knowledge we have on the problem is not stated, while it could have been helpful in solving the problem efficiently. We know, for example, that in the rightmost column D + D is neces­ sarily equal to T or 10 + T since there is no carry. We know that on the leftmost column R is equal to D + G or D + G + 1 since there is no letter on the left of R. More generally, for the third column for example, we know that (N + R = B) V (N + R = 10 +B) V (N + R + 1 = B) V (N + R + 1 = 10 +B). All these constraints (six in the cryptogram of Fig. 1) are predicates, but no al­ ready known specific algorithm can handle them (they are not arithmetic relations, but disjunctions of several arithmetic relations).

The table below presents the number of backtracks (#bt) and cpu-time performances of solving the cryp­ togram with ILOG Solver 4.0 (maintaining arc consis­ tency during search) on a Pentium Pro 200, with or with­ out the GAC-schema and the 6 additional constraints, and with or without the use of the minimal domain dy­ namic variable ordering (DVO).

Of course it is a very small illustration that is given here with that sample problem. In this problem, indeed, the additional constraints are only added to improve the search. They are not necessary to encode the problem: the first two constraints were already ensuring that the solutions of the constraint network were the solutions of the cryptogram.

7 Conclusion

While arc consistency had been widely studied by the CSP community, there did not exist any algorithm that efficiently achieves arc consistency on non-binary con­ straints. Thus, we presented GAC-schema, which is built to take into account the last improvements available on binary constraints (AC-7 like schema). We saw that it is even more important than on binary constraints to use such improvements (e.g. multidirectionality). With specialized instantiations, this schema is capable of effi­ ciently dealing with predicates, positive constraints, or negative constraints. The perspectives of this work are to propose other instantiations of the schema in order to improve arc consistency processing on some other types of constraint representations frequently occurring in in­ dustrial problems.