Some Practicable Filtering Techniques for the Constraint Satisfaction Problem

1 Introduction

Constraint satisfaction problems (CSPs) are used more and more to solve combinatorial problems arising in ar­ tificial intelligence. They involve finding an assignment of values to variables subject to constraints. This is a NP-hard task. So, the time needed by a primitive back­ track search to find such an assignment will probably be strongly affected by thrashing because it will fall many times into the same local inconsistencies. Thus filtering techniques are used to remove some local inconsistencies before or during the search. To find the suitable level of consistency to achieve we have to both consider the prun­ ing efficiency of the filterings involved, and their time and space complexities. Obviously, the overhead caused by removing local inconsistencies has to be outweighted by its gain, which can change depending on the problem to solve. On very easy and very small CSPs, filtering tech­ niques are useless because we can quickly find a solution or prove the inconsistency. But it can be advantageous to use an algorithm that wastes a few seconds on easy CSPs if it can save many minutes (hours ?) on hard prob­ lems. A good illustration is the efficiency of maintain­ ing arc consistency during search (MAC) on hard CSPs [Bessiere and Regin, 1996] . On these problems, MAC can outperform forward checking (FC) which maintains a lower level of local consistency. The harder a CSP is , the more useful filtering techniques are. So, maintaining a local consistency during search is essential in order to deal with large and hard problems . Obviously, whatever the level of local consistency maintained may be, some pathological CSPs which are hard to solve can be found. But the more pruningful the filtering technique is , the more seldom these CSPs are.

Arc consistency (AC) filtering is widely used on bin­ ary CSPs because it removes some values that cannot belong to any solution with a low space and time com­ plexity. On the other hand, strong path consistency can remove more inconsistencies but is never used because of its huge complexity and because it changes the struc­ ture of the problem by adding constraints. Indeed, path consistency algorithms remove compatible pairs of val­ ues that cannot be extended to a consistent instantiation including any third variable. If a path inconsistent pair of values between two independent variables is found , it is removed from the corresponding universal relation and so the structure of the constraint graph is changed. This is a real drawback, especially when we deal with sparse problems because the resulting constraint graph is often complete. The second important drawback is the lost of semantics. In real applications, a constraint is rarely represented by a boolean matrix or a set of compatible pairs of values. It is represented by a predicate which has a particular semantics(#, ~' ... ),and this semantics is lost when some allowed pairs of values are removed. This leads to the generation of the boolean matrix, and so to space intractability.

The aim of this paper is to study the filtering tech­ niques that can be used in practice. So, we only care about those that do not change the constraints and that do not require to have the constraints in extension, i.e. those that only remove values in the variable domains.

2 Definitions and notations

A binary CSP P = (X, V, C) is a set X = { i, j, . .. } of n variables, each taking value in its respective finite domain D;, Dj, ... elements of V, and a set C of e binary constraints. dis the size of the largest domain.

A binary constraint C;j is a subset of the cartesian product D; x Dj that denotes the compatible pairs of val­ ues fori and j. We note C;j(a, b) =true to specify that ((i, a), (j, b)) E Cij· We then say that (j, b) is a support of(i, a) on C;j. With each CSP we associate a constraint graph in which nodes represent variables and arcs con­ nect pairs of variables which are constrained explicitly. The neighborhood of i is the set of variables linked to i in the constraint graph. A domain V' = { D:, Dj, ... } is a sub-domain of V = { D;, Dj , ... } if Vi, D: ~ D; . An instantiation of a set of variables S is an indexed set of values {IihEs s.t. Vj E S Ij E Dj. An instantiation I of S satisfies a constraint C;j if { i, j} Cf: S or C;j (I;, Ij) is true. An instantiation is consistent if it satisfies all the constraints. A solution of P = (X, V, C) is a consistent instantiation of X. A value ( i, a) is consistent if there is a solution I such that I; = a, and a CSP is consistent if it has at least one solution. In the following we denote by P ID,={a} the CSP obtained by restricting D; to {a} in P.

3 Overview on filtering techniques

Filtering techniques may detect inconsistency or remove some local inconsistencies in order to make the search easier. They look for partial instantiations that cannot be extended to a solution and remove them.

Fig. 1 presents the properties corresponding to the filtering techniques studied. The best AC algorithms are AC-6 [Bessiere, 1994] with the O(ed 2 ) optimal worst-case time complexity and O(ed) worst-case space complexity, and AC-7 [Bessiere et al., 1995], which deals with the bidirectionality of constraints to improve AC-6.

k-consistency, i.e. ( k -1, 1 )-consistency [Freuder, 1985], removes the consistent instantiations of length k - 1 that cannot be extended to a consistent instantiation includ­ ing any additional kth variable. The time and space complexity of k-consistency algorithms is polynomial in k. Furthermore, if k ;?: 3, k-consistency changes the structure of the p~oblem . So, only 2-consistency (i.e.

• ·A binary CSP is (i, j)-consistent iff '<lk E X , Dk i 0, and any consistent instantiation of i variables can be extended to a consistent instantiation including any j additional variables.
• ·A domain D; is arc consistent iff, '<Ia E D;, '<lj E X s .t . C;i E C, there exists bE Dj s.t . C;j(a, b). A CSP is arc consistent ((1, 1)­ consistent) iff '<ID; ED , D; i 0 and D; is arc consistent .
• ·A pair of variables ( i, j) is path consistent iff'</( a, b) E C ij , '<lk E X, there exists c E Dk s.t. C;k(a , c) and C jk{b , c). A CSP is path consistent ((2, 1)-consistent) iff'<li, j EX, (i, j) is path consistent.
• A binary CSP is strongly path consistent iff it is node-consistent , arc consistent and path consistent.
• ·A binary CSP is path inverse consistent iff it is (1, 2)-consistent i.e . '<l(i, a)ED '<lj,kEX s.t . #i##j, 3(j, b)ED and (k, c)ED s.t. C;;(a, b) 1\ C;k(a, c) 1\ Cjk(b, c)
• A binary CSP is neighborhood inverse consistent iff '</(i, a)ED, (i, a) can be extended to a consistent instantiation including the neighborhood of i.
• ·A binary CSP is restricted path consistent iff Vi E X, D; is a non empty arc consistent domain and, '<l(i, a) E D, for all j E X s.t . (i , a) has an unique support b in Dj, for all k EX linked to both i and j, 3c E Dk s.t. C;k(a, c) 1\Cjk (b, c).
• A binary CSP P is singleton arc consistent iff Vi E X , D i i 0 and '</(i, a) ED , P ID;={a} has an arc consistent sub-domain.
• A binary CSP P is singleton restricted path consistent iff ViE X , D; i 0 and '<l(i , a) ED, P ID;={a} has a restricted path consistent sub-domain .

Figure 1: The local consistencies studied.

arc consistency.) can be used in practice. However, path consistency (3-consistency) being widely studied, we will compare strong path consistency (enforcing both arc and path consistency) with the other filtering tech­ niques removing values. The best PC algorithms are PC5 [Singh, 1995] with O(n 3 d 3 ) worst-case time complex­ ity and O(n 3 d 2 ) worst-case space complexity, and PC-8 [Chmeiss and Jegou, 1996] which requires smaller space (O(n 2 d) 1 ) but with O(n 3 d 4 ) worst-case time complexity.

Arc consistency being a low level of consistency and path consistency leading to important drawbacks, Ber­ landier proposed the restricted path consistency (RPC) in [Berlandier, 1995]. This filtering technique removes the arc inconsistent values but in addition it checks the path consistency of the pairs of values involving a weakly supported value. The idea is that if a value (i, a) has an unique support (j, b) on C;j , it may be advantageous to check the path consistency of ((i, a), (j, b)) because the deletion of this pair leads to the arc inconsistency of (i, a) . So, RPC uses path inconsistency to remove values but does not delete any pair of values. This allows to re­ move more values than AC while avoiding the drawbacks of PC. The RPC algorithm in [Berlandier, 1995] has O(end 3 ) worst-case time complexity and O(end + ed 2 ) worst-case space complexity. But this algorithm is not optimal in time.

1 Remark that we still need a 0( n 2 d 2 ) data structure for the constraints representation.

'Another way to avoid the drawbacks of k-consistency is to consider the "opposite" property. k-inverse consist­ ency (i .e. (1 , k -I)-consistency [Freuder, 1985]) removes the values that cannot be extended to a consistent in­ stantiation including any k - 1 additional variables. The constraint graph is unchanged by this filtering technique and the space required to enforce it is linear. However, as for k-consistency, the worst-case time complexity is polynomial in k, and so, inverse consistency quickly be­ comes prohibitive when k grows. The first level removing more values than arc consistency is path inverse consist­ ency (k = 3) . Obviously, the more k is important , the more pruningful k-inverse consistency is , but we cannot reasonably remove the n-inverse inconsistent values. A good compromise is to make sure that each value can be extended to a consistent instantiation including its neighborhood. This filtering technique called neighbor­ hood inverse consistency (NIC)[Freuder and Elfe, 1996] adapts the level oflocal inverse consistency to the number of constraints involving the variable. This is an efficient method on sparse problems but its exponential worst­ case time complexity cannot guarantee a reasonable cpu time. ·

Singleton consistency is a new class of filtering tech­ niques. It is based on the fact that if a value (i , a) is con­ sistent , then the CSP obtained by restricting the domain of i to the singleton {a} is consistent . So, if P ln,={a} is inconsistent, we can delete ( i, a) . 0 bviously find­ ing if P ln,={a} is consistent may be costly. Therefore, we only check if a local consistency holds in P In, ={ a}. For example, a CSP is singleton arc consistent if it does not have any empty domain, and V(i , a) E V , P ln,={a} has a non empty arc consistent sub-domain. Any AC algorithm can be used to determine whether achieving arc consistency in P ln,={a} can yield a domain wipe out, but a lazy approach (such as LAC7 [Schiex et al. , 1996]) is sufficient. The singleton consistency can be used with any algorithm removing inconsistent values as those studied in this paper. If the local consistency can be enforced in a polynomial time in P ln, ={a} > the cor­ responding singleton consistency has a polynomial worst­ case time complexity too.

Since AC algorithms can incrementally propagate the deletion of a value, we propose the algorithm of Fig. 2. It can easily be adapted to enforce a singleton consist­ ency with a stronger pruning efficiency, such as SRPC or SPIC.

4 Pruning efficiency

4.1 Qualitative study

In order to compare the pruning efficiency of the local consistencies we study, we introduce the following trans­ itive relation. We say that a local consistency LC is stronger than another local consistency LC' if in any CSP in which LC holds, LC' holds too. For example and by definition, RPC is stronger than AC. Therefore , a RPC algorithm removes at least all the arc inconsist­ ent values. Consequently, the domain of RPC(P) is a sub-domain of the domain ·Of AC(P) whatever P may be. A local consistency LC is strictly stronger than an­ other local consistency LC' if LC is stronger than LC' and there is at least one CSP in which LC' holds and LC does not hold.

Theorem 4.1 If I X 12:3, path inverse consistency is stronger than restricted path consistency.

Proof. First , let us show that PIC is stronger than arc consistency if I X 12:3. For all (i, a) E D and C;j E C, let k be any third variable. PIC implies the existence of (j, b) E D and (k , c) ED such that C;j(a , b) , C;k(a , c) and Cjk(b , c). So, for all (i , a) ED and C;j E C, there exists a support (j, b) E D. The second property of RPC is a trivial consequence of PIC. If PIC holds, any value (i , a) ED can be extended to a consistent instantiation including any two other variables. So, if (i , a) has an unique support (j, b) on C;j we are sure that whatever k is, ( i , a) can be extended to a consistent instantiation I including j and k s.t . Ij = b. ·

Theorem 4.2 If I X 12:3 and the constraint graph is con­ nected, neighborhood inverse consistency is stronger than path inverse consistency.

Proof. see [Debruyne and Bessiere, 1997]

·

Theorem 4.3 If I X 12:3, singleton arc consistency is stronger than path inverse consistency.

Proof. Suppose that a singleton arc consistent value (i, a) is not path inverse consistent . Let j and k be two variables s.t . (i, a) cannot be extended to a consistent instantiation including j and k . (i , a) being singleton arc consistent, let D' be an arc consistent sub domain of P In,={ a} and b a value in Dj. There exists a value c E D~ supporting (j, b) on Cjk· Since b and c are in an arc consistent sub-domain of P ln, ={a} > C;j(a , b) and C;k(a, c). We have therefore a contradiction since (a, b, c) is a consistent instantiation of {i, j , k} . ·

Theorem 4.4 Singleton restricted path consistency ts stronger than singleton arc consistency.

Proof. Trivial since restricted path consistency is -stronger than arc consistency. ·

Theorem 4.5 Strong path consistency is stronger than singleton arc consistency.

Proof. We have to prove that if a value (i, a) is singleton arc inconsistent, a strong path consistency algorithm re­ moves it . First, let us show that if a value (j, b) is arc inconsistent in P ln,={a} and (a, b) E Ctj then (a, b) is path inconsistent w.r.t. P (by induction on the number of arc inconsistent values deleted before (j, b)). If (j, b) is the first value deleted by an AC algorithm because it has no support in Dk, (a, b) cannot be extended to a consistent instantiation of {i, j, k}. If after the deletion of marc inconsistent values, (j, b) has to be removed be­ cause it no longer has a support in Dk, all the supports of (j, b) on Cjk have already been deleted in P ln,={a}· Thus, by induction hypothesis (a, c) is path inconsistent in P for all (k, c) compatible with (j, b). So, (a, b) is path inconsistent in P .

According to this lemma, if a value (i, a) is singleton arc inconsistent because AC clears the domain of j in PIn,={ a} , path consistency removes (a, b) from Ctj for all bE Dj and AC deletes (i, a). ·

SAC and strong PC are strongly related. In (Me Gregor, 1979], Me Gregor proposed a strong path consistency algorithm that can be modified to achieve SAC. This algorithm repeatedly enforces arc consistency on P lv,={a} for all (i, a) E D. If a wipe out occurs, (i , a) is removed, otherwise (a, c) is deleted from Ctk for all (k, c) removed by arc consistency in P ln,={a}· The algorithm stops when it can no longer detect incon­ sistent values or path inconsistent pairs of values. A SAC algorithm is obtained by omitting deletions of pairs of values in this algorithm. So, strong PC removes more values only when the propagation of the deletions of pairs of values leads to some additional value deletions.

Fig. 3 shows the relations between the filtering tech­ niques studied. A continuous arrow from A to B means that the local consistency A is strictly stronger than B. There is a crossed line between A and B if A and B are incomparable w . ~.t. the "stronger" relation. If A is not stronger than B ( B is strictly stronger than A or A and B are incomparable), a CSP in which A holds and B does not hold can be found in [Debruyne and Bessiere, 1997] . The "stronger" relation does not induce a total ordering. For instance, NIC and SRPC are incomparable.

4.2 Experimental evaluation

The study in 4.1 gives no quantitative information. A local consistency can be stronger than another while per­ forming few additional value deletions. Furthermore, a local consistency LC can remove more values than an­ other local consistency LC' on most of the CSPs while being incomparable with LC' because of some particular CSPs.

Fig. 4 shows on which random CSPs the local consist­ encies are useful to detect inconsistency. The CSP gener­ ator involves four parameters : n the number of variables , d the common size of all the initial domains, PI the pro­ portion of constraints in the network (p1 =1 corresponds to the complete graph) and P2 the proportion of forbid­ den pairs of values in a constraint (the tightness) 2 . The problems of Fig. 4 have 20 variables, 10 values in each domain, and for each possible pair (PI, P2), 500 prob­ lems were generated. The continuous line shows for each density the minimal tightness for which the 500 random CSPs are all inconsistent. For each filtering technique, Fig. 4 presents the pairs (p1, P2) for which the given local inconsistency is detected on all the generated problems. For example, for AC the limit is 0.69 at density 0.5. This means that for a smaller tightness, there is at least one of the 500 problems on which AC does not remove all the values.

Restricted path consistency is very close to PIC al­ though it requires much less computational effort. To . achieve RPC, we have to try to extend a value (i, a) to a consistent 3-tuple involving {i , j, k} only if (i, a) has an unique support in Dj. It is sufficient to remove most of the values deleted by PIC. As said in section 4.1 , SAC is close to strong path consistency which re­ moves more inconsistent values only when there is an important propagation of pairs of values removed. Al­ though SRPC and strong PC are incomparable, SRPC can detect more inconsistent values on most of the CSPs. All these polynomial filterings have a similar behavior. They show difficulties in inconsistency detection on dense problems with loose constraints. It was predicted in [van Beek, 1994]. NIC has a very different behavior. On very dense CSPs, checking if a value can be extended to a con­ sistent instantiation including its neighborhood is close to checking the consistency of the value. However, on the generated problems with a density between 0.2 and Tightness

2 See [Frost et al., 1996] for a complete description of the uniform random CSP generator we used.

0.55, NIC prunes fewer values than SAC, strong PC, and is the less efficient (if we exclude strong PC) on CSPs SRPC. involving many constraints or having tight constraints. 5 Time efficiency The most promising filtering techniques are SAC and RPC. SAC removes most of the strong path inconsistent values while requiring less cpu time than PIC. The RPC algorithm used is non optimal and does not propagate the value deletions as soon as possible. This explains the relatively bad time performances for tightness between 0.5 and 0.8 at density 0.25. However, RPC may remove much more values than AC.

6 Conclusion

In this paper we studied the filtering techniques that are practicable on large CSPs, i.e. those that do not change the constraints. When the aim is detecting inconsistency, SRPC and NIC are the most powerful local consistencies. However, they are expensive in time and the exponential worst case time complexity of NIC makes it unusable on some dense CSPs. Two promising local consistencies are SAC and RPC, SAC having a good cpu time to number of deleted values ratio, and RPC requiring little additional cpu time compared to AC while removing most of the path inverse inconsistent values.