R. Debruyne and C. Bessiere

Volume 14, 2001

**Links to Full Text:**

Enforcing local consistencies is one of the main features of constraint reasoning. Which level of local consistency should be used when searching for solutions in a constraint network is a basic question. Arc consistency and partial forms of arc consistency have been widely studied, and have been known for sometime through the forward checking or the MAC search algorithms. Until recently, stronger forms of local consistency remained limited to those that change the structure of the constraint graph, and thus, could not be used in practice, especially on large networks. This paper focuses on the local consistencies that are stronger than arc consistency, without changing the structure of the network, i.e., only removing inconsistent values from the domains. In the last five years, several such local consistencies have been proposed by us or by others. We make an overview of all of them, and highlight some relations between them. We compare them both theoretically and experimentally, considering their pruning efficiency and the time required to enforce them.

Journal of Artificial Intelligence Research 14 (2001) 205-230 Submitted 12/00; published 5/01 Domain Filtering Consistencies Romuald Debruyne Romuald.Debruyne@emn.fr Member of the Coconut group Ecole des Mines de Nantes, La Chantrerie, 4, Rue Alfred Kastler, 44307 Nantes Cedex 3 - France Christian Bessi`ere bessiere@lirmm.fr Member of the Coconut group LIRMM - CNRS UMR 5506, 161 rue Ada, 34392 Montpellier Cedex 5 - France Abstract Enforcing local consistencies is one of the main features of constraint reasoning. Which level of local consistency should be used when searching for solutions in a constraint network is a basic question. Arc consistency and partial forms of arc consistency have been widely studied, and have been known for sometime through the forward checking or the MAC search algorithms. Until recently, stronger forms of local consistency remained limited to those that change the structure of the constraint graph, and thus, could not be used in practice, especially on large networks. This paper focuses on the local consistencies that are stronger than arc consistency, without changing the structure of the network, i.e., only removing inconsistent values from the domains. In the last five years, several such local consistencies have been proposed by us or by others. We make an overview of all of them, and highlight some relations between them. We compare them both theoretically and experimentally, considering their pruning efficiency and the time required to enforce them. 1. Introduction There are more and more applications in artificial intelligence that use constraint networks (CNs) to solve combinatorial problems, ranging from design to diagnosis, resource allocation to car sequencing, natural language understanding to machine vision. Finding a solution in a constraint network involves looking for a set of value assignments, one for each variable, so that all the constraints are simultaneously satisfied (Meseguer, 1989; Tsang, 1993). This task is NP-hard and many exponential time algorithms have been proposed to solve this problem. These algorithms, which make a systematic exploration of the search space, all have backtracking as a basis. As long as the unassigned variables have values consistent with the partial instantiation, they extend it by assigning values to variables. Otherwise, a dead-end is reached and some previous assignments have to be changed before going on with the partial instantiation extension. The explicit constraints of the network together induce some implicit constraints. Since basic search algorithms do not record these implicit constraints, they waste time by repeatedly detecting the local inconsistencies caused by them. Filtering techniques are essential to reduce the size of the search space and so to improve the efficiency of search algorithms. They can be used during a preprocessing step to remove once and for all some local inconsistencies that otherwise would have been repeatedly found during search (Dechter & Meiri, 1994). They can also be maintained during search. cfl2001 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved. Debruyne & Bessi`ere Search algorithms differ in the kind of local consistency they achieve after each choice of a value for a variable. Most of them enforce partial arc consistency, going from forward checking (FC,Golomb & Baumert, 1965; Haralick & Elliott, 1980), which only removes the values directly arc inconsistent with the last assignment, to really full look-ahead (RFL, Gaschnig, 1974), which achieves full arc consistency. Arc consistency (AC) and partial forms of arc consistency are widely used for two reasons. First, they have low space and time complexities, while path consistency and higher levels of k-consistency, which were for a long time the only other options, are prohibitive and can change the structure of the network. Moreover, until 1995, more pruningful local consistencies seemed uninteresting since experimental evaluations of search algorithms showed that the limited local consistency used by forward checking was the best choice (Nadel, 1988; Kumar, 1992; Bacchus & van Run, 1995). This conclusion is not surprising since the comparisons were made on very small and easy constraint networks. On such problems, the additional cost of pruning more values could not be outweighed by the search savings. However, the harder a constraint network is, the more useful filtering techniques are. More recent works (Bessi`ere & R'egin, 1996; Sabin & Freuder, 1994; Grant & Smith, 1996) testing search algorithms at the threshold (Cheeseman, Kanefsky, & Taylor, 1991), where most of the hard problems are expected to be, show that using more pruningful local consistencies can be worthwhile. Their conclusion is that maintaining arc consistency during search (MAC), namely achieving AC both after the choice of a value for a variable and after the refutation of such a choice, outperforms forward checking on hard problems. The good behavior of MAC is even more significant on large problems, especially when domains are large. It is conceivable that on very difficult instances, maintaining an even more pruningful local consistency may pay off. Obviously, such an algorithm would waste seconds on easy CNs but it would save many minutes (hours ?) on very hard problems, reducing the set of pathological CNs on which search is really prohibitive. In this paper we study the local consistencies as preprocessing filtering techniques. This is a preliminary work before trying to determine which local consistency is the most advantageous to be maintained during search. In the last five years, many new local consistencies have been proposed. In the remaining of this paper, we focus our attention on those that leave unchanged the structure of the network since they are the only able to be used on large CNs. In addition to an overview of these local consistencies that only remove inconsistent values, we both compare, theoretically and experimentally, their pruning efficiency and the time needed to enforce them. 2. Definitions and Notations A network of binary constraints P = (X ; D; C) is defined by a set X = fi; j; : : : g of n variables, each taking value in its respective finite domain Di; Dj; : : : elements of D, and a set C of e binary constraints. d is the size of the largest domain. A binary constraint Cij is a subset of the Cartesian product Di Theta Dj that denotes the compatible pairs of values for i and j. We denote Cij(a; b) = true to specify that ((i; a); (j; b)) 2 Cij. We then say that (j; b) is a support for (i; a) on Cij. Checking whether a pair of values is allowed by a constraint is called a constraint check . With each CN we associate a constraint graph in which nodes represent variables and arcs connect pairs of variables that are constrained 206 Domain Filtering Consistencies explicitly. c is the number of 3-cliques in the constraint graph and g is the maximum degree of a node in the constraint graph. The neighborhood of i is the set of variables adjacent to i in the constraint graph. A domain D0 = fD0i; D0j; : : :g is a sub-domain of D = fDi; Dj; : : :g if 8i; D0i ` Di. An instantiation I of a set of variables S is a set of value assignments fIjgj2S, one for each variable belonging to S, s.t. 8j 2 S; Ij 2 Dj. An instantiation I of S satisfies a constraint Cij if fi; jg 6` S or Cij(Ii; Ij) is true. An instantiation is consistent if it satisfies all the constraints. A pair of values ((i; a); (j; b)) is path consistent if for all k 2 X s.t. j 6= k 6= i 6= j, this pair of values can be extended to a consistent instantiation of fi; j; kg. (j; b) is a path consistent support for (i; a) if (a; b) 2 Cij and ((i; a); (j; b)) is path consistent. A solution of P = (X ; D; C) is a consistent instantiation of X . A value (i; a) is consistent if there is a solution I such that Ii = a, and a CN is consistent if it has at least one solution. We denote by P jDi=fag the CN obtained by restricting Di to fag in P . If LC is a local consistency, a CN P is not LC-consistent iff LC does not hold on P . A CN P is LC-inconsistent iff we cannot obtain a LC-consistent constraint network by deletion of some local inconsistencies in P . If a local consistency LC is used to detect the inconsistency of instantiations no longer than 1, we can say that a CN P = (X ; D; C) is LC-inconsistent iff there is no sub-domain D0 of D such that LC holds on (X ; D0; C). 3. The Local Consistencies Studied Filtering techniques can be used to detect the inconsistency of a CN, and under some assumptions, they can ensure a backtrack-free search (Freuder, 1982, 1985). However, their usual purpose is not to find a solution in a constraint network. They remove some local inconsistencies and so delete some regions of the search space that do not contain any solution. The resulting CN is equivalent to the initial one since the set of solutions is unchanged, but if substantial reductions are made the search becomes easier. In this section we review the basis of arc consistency, k-consistency, restricted path consistency, and inverse consistencies. Furthermore, we extend the idea of restricted path consistency to k-restricted path consistency and Max-restricted path consistency. We propose a new class of local consistencies called singleton consistencies. We also show a property of path inverse consistency that can be used to have an optimal worst case time complexity in a path inverse consistency algorithm (Debruyne, 2000). Arc consistency The most widely used local consistency is arc consistency. It is based on the notion of support. A value is viable as long as it has at least one compatible value in the domain of each neighboring variable. An AC algorithm has to remove the values that have no support on a constraint. As in most of the filtering techniques, the value deletions have to be propagated through the network since they can lead to the arc inconsistency of some values that were previously viable. k-consistency A consistent instantiation of length k-1 is k-consistent (i.e., (k-1, 1)- consistent in the formalism of Freuder, 1985) if it can be extended to any additional kth variable. The time and space complexities of enforcing k-consistency are polynomial with the exponent dependent on k. If k * 3, the constraints have to be represented in extension to store the (k-1)-tuples deleted, and the structure of the network can be changed. This leads to huge space requirements and subsequently important cpu time costs. In practice, 207 Debruyne & Bessi`ere only 2-consistency, which is arc consistency in binary CNs, can be used. Although path consistency (PC, namely 3-consistency) cannot be used on large CNs, our experiments will involve strong path consistency (namely enforcing both arc and path consistency) because PC has been widely studied. Restricted path consistency The aim of Berlandier when he proposed restricted path consistency (RPC, Berlandier, 1995) was to remove more inconsistent values than AC while avoiding the drawbacks of path consistency. Even the most efficient PC algorithms have to try to extend all the pairs of values (even those between two variables that are not neighbors) to any third variable. The basis of RPC is to avoid most of this prohibitive work. RPC performs only the most pruningful path consistency checks, namely those able to directly delete a value. In addition to AC, an RPC algorithm checks the path consistency of the pairs of values ((i; a); (j; b)) such that (j; b) is the only support for (i; a) in Dj. If such a pair is path inconsistent, its deletion would lead to the arc inconsistency of (i; a). Thus (i; a) can be removed. These few additional path consistency checks allow detecting more inconsistent values than AC without having to delete any pair of values, and so leaving unchanged the structure of the network. k-restricted path consistency We can extend the idea of RPC to a more pruningful local consistency. If RPC holds, the values that have only one support on a constraint are such that this support is path consistent. Checking the path consistency of more supports can remove even more values without falling into the traps of PC. k-restricted path consistency (k-RPC, Debruyne & Bessi`ere, 1997a) looks for a path consistent support on a constraint for the values that have at most k supports on this constraint. RPC is 1-RPC and AC corresponds to 0-RPC. If k-RPC holds, to achieve (k+1)-RPC we only have to check the values that have exactly (k+1) supports on a constraint and to propagate their possible deletion. So, it is possible to achieve AC, RPC, 2-RPC and so on, each time reusing previous filtering effort. This adaptive enforcement can be stopped as soon as each value has at least one path consistent support on each constraint, the constraint network being d-RPC where d is the size of the largest domain. Indeed, if after achieving k-RPC all the values have at most k supports on each constraint, k0-RPC holds for all k0 ? k. Max-restricted path consistency A constraint network is Max-restricted path consistent (Max-RPC, Debruyne & Bessi`ere, 1997a) if all the values have at least one path consistent support on each constraint, whatever is the number of supports. From the pruning efficiency point of view, Max-RPC is an upper bound for k-RPC. Achieving Max-RPC involves deleting all the k-restricted path inconsistent values for all k. However, achieving Max-RPC can be less expensive than enforcing a high level of k-RPC. As opposed to MaxRPC, to achieve k-RPC we have to look for the values that have at most k supports on a constraint to know the values for which a path consistent support has to be found. This can be expensive if k is great, the algorithm having to look for k+1 supports for each value on each constraint. Unconditionally looking for a path consistent support avoids this costly extra work. k inverse consistency The aim of Freuder and Elfe when they proposed inverse consistency (Freuder & Elfe, 1996) was to achieve high order local consistencies with a good space complexity. A k-consistency algorithm removes the instantiation of length k-1 that cannot 208 Domain Filtering Consistencies be extended to any kth variable. It requires O(nkGamma 1dkGamma 1) space to keep track of the deleted instantiations. Space requirements are no longer a problem with k inverse consistency ((1, k-1)-consistency), which removes the values that cannot be extended to a consistent instantiation including any k-1 additional variables. Its linear space complexity would allow using it on large CNs. However, its worst case time complexity is polynomial with the exponent dependent on k, which restricts its use to small values of k. Path inverse consistency The first level of k inverse consistency removing more values than AC is path inverse consistency (PIC, k = 3). By definition, (i; a) is path inverse consistent if it can be extended to all the 3-tuples of variables containing i. However, as said in (Freuder & Elfe, 1996), not all the 3-tuples need to be checked to enforce PIC. Only one of the tuples (i; j; k) and (i; k; j) has to be checked. Moreover, if i is linked to neither j nor k, (i; a) can be deleted because of (i; j; k) only if all the values of j or k are path inverse inconsistent. In such a case, checking (i; j; k) is useless since PIC detects the inconsistency of the network when processing j or k. Neighborhood inverse consistency Since k inverse consistency is polynomial with the exponent dependent on k, checking the k inverse consistency of all the values is prohibitive if k is great. However, if the variables are not uniformly constrained, it would be worthwhile to adapt the level of k inverse consistency to the number of constraints involving them, focusing filtering effort on the most constrained variables (as it is done for adaptive consistency Dechter & Pearl, 1988). This is the basis of neighborhood inverse consistency (NIC, Freuder & Elfe, 1996), which removes the values that cannot be extended to a consistent instantiation including all the neighboring variables. We have to point out that the behavior of NIC is dependent on the structure of the constraint graph. If two variables i and j are not neighbors, we can add a universal constraint allowing all the pairs of values (a; b) 2 Di Theta Dj between i and j. The resulting CN is equivalent to the initial one since it has the same set of solutions. However, as opposed to the other filterings studied in this paper, NIC is affected by this change since it can remove more values. Obviously, this process increases time complexity. On complete constraint networks, NIC tries to extend all the values to a whole solution, namely deleting all the globally inconsistent values (named variable completability in Freuder, 1991). This is a far more difficult task than looking for one solution. To be cost effective, NIC has to be used only on sparse CNs, where the degree of the variables is small. Singleton consistencies If a value (i; a) is consistent, the constraint network obtained by restricting Di to the singleton fag is consistent. Singleton consistencies are a class of filtering techniques based on this remark. To detect the inconsistency of a value (i; a), a singleton consistency filtering technique checks whether a given local consistency can detect the possible inconsistency of P jDi=fag. For example, singleton arc consistency (SAC, Debruyne & Bessi`ere, 1997b) deletes the values (i; a) such that P jDi=fag has no arc consistent sub-domain.1 SAC has been inspired by the strong path consistency algorithm proposed by McGregor(McGregor, 1979). A SAC algorithm is obtained by omitting the deletions 1. Any AC algorithm can be used to know whether enforcing AC on P jDi=fag leads to a domain wipe out, but a lazy approach (such as LAC7 Schiex, R'egin, Gaspin, & Verfaillie, 1996) is sufficient. 209 Debruyne & Bessi`ere ffl A binary CN is (i; j)-consistent iff 8i 2 X , Di 6= ; and any consistent instantiation of i variables can be extended to a consistent instantiation including any j additional variables. ffl A value a 2 Di is arc consistent iff, 8j 2 X s.t. Cij 2 C, there exists b 2 Dj s.t. Cij(a; b). A domain Di is arc consistent iff, 8a 2 Di; (i; a) is arc consistent. A CN is arc consistent ((1, 1)-consistent) iff 8Di 2 D, Di is a non empty arc consistent domain. ffl A pair of values ((i; a); (j; b)) is path consistent iff 8k 2 X , there exists c 2 Dk s.t. Cik(a; c) and Cjk(b; c), otherwise it is path inconsistent. A CN is path consistent ((2, 1)-consistent) iff no path inconsistent pair of values is allowed. ffl A binary CN is strongly path consistent iff it is node consistent, arc consistent and path consistent. ffl A binary CN is path inverse consistent iff it is (1, 2)-consistent i.e., 8(i; a)2D 8j; k2X s.t. j 6= i 6= k 6= j, 9(j; b)2D and 9(k; c)2D s.t. Cij(a; b) ^ Cik(a; c) ^ Cjk(b; c) ffl A binary CN is neighborhood inverse consistent iff 8(i; a)2D, (i; a) can be extended to a consistent instantiation including the neighborhood of i. ffl A binary CN is restricted path consistent iff 8i 2 X , Di is a non empty arc consistent domain and, 8(i; a) 2 D, for all j 2 X s.t. (i; a) has an unique support b in Dj, for all k 2 X linked to both i and j, 9c 2 Dk s.t. Cik(a; c) ^Cjk(b; c). ffl A binary CN is k-restricted path consistent iff 8i 2 X , Di is a non empty arc consistent domain and, 8(i; a) 2 D, for all Cij 2 C s.t. (i; a) has at most k supports in Dj, 9b 2 Dj s.t. Cij(a; b) and 8k 2 X linked to both i and j, 9c 2 Dk s.t. Cik(a; c) ^Cjk(b; c). ffl A binary CN is max-restricted path consistent iff 8i 2 X , Di is a non empty arc consistent domain and, 8(i; a) 2 D, for all Cij 2 C, 9b 2 Dj s.t. Cij(a; b) and 8k 2 X linked to both i and j, 9c 2 Dk s.t. Cik(a; c) ^Cjk(b; c). ffl A binary CN P is singleton arc consistent iff 8i 2 X , Di 6= ; and 8(i; a) 2 D, P jDi=fag has an arc consistent sub-domain. ffl A binary CN P is singleton restricted path consistent iff 8i 2 X , Di 6= ; and 8(i; a) 2 D, P jDi=fag has a restricted path consistent sub-domain. Figure 1: The mentioned local consistencies. 210 Domain Filtering Consistencies Name of Worst case Worst case the algorithm time complexity space complexity AC7 (Bessi`ere, Freuder, & R'egin, 1999) O(ed2)(Lambda ) O(ed) RPC2 (Debruyne & Bessi`ere, 1997a) O(en + ed2 + cd2)(Lambda ) O(ed + cd) Max RPC1 (Debruyne & Bessi`ere, 1997a) O(en + ed2 + cd3)(Lambda ) O(ed + cd) PC5 (Singh, 1995) O(n3d3)(Lambda ) O(n3d2) PC8 (Chmeiss & J'egou, 1996) O(n3d4) O(n2d)2 PIC1 (Freuder & Elfe, 1996) O(en2d4) O(n) PIC2 (Debruyne, 2000) O(en + ed2 + cd3)(Lambda ) O(ed + cd) NIC1 (Freuder & Elfe, 1996) O(g2(n + ed)dg+1) O(n) SAC1 (Debruyne & Bessi`ere, 1997b) O(en2d4) O(ed) SRPC1 (Debruyne & Bessi`ere, 1997b) O(en + n2(e + c)d4) O(ed + cd) (Lambda ) optimal worst case time complexity. Table 1: The most efficient algorithms achieving the mentioned local consistencies.3 of pairs of values in that algorithm. Many other singleton consistencies can be considered since any local consistency can be used to detect the possible inconsistency of the CNs P jDi=fag with (i; a) 2 D. If a local consistency can be enforced in a polynomial time, the corresponding singleton consistency also has a polynomial worst case time complexity. The formal definitions of the local consistencies studied in this paper are presented in Figure 1. Table 1 recalls the time and space complexities of the most efficient algorithms enforcing them. The worst case time complexity of SAC1, SRPC1, and NIC1 have not been proved to be optimal. 4. Relations between PIC, RPC and Max-RPC To highlight the relations between PIC, RPC and Max-RPC, let us show a property of path inverse consistency. As shown in (Debruyne, 2000), if we assume that the constraint network is arc consistent, enforcing PIC requires checking even less 3-tuples than those mentioned in (Freuder & Elfe, 1996). If (i; a) is arc consistent, it can be extended to any 3-tuple (i; j; k) such that there is no constraint between j and k. Indeed, (i; a) has a support (j; b) on Cij and a support (k; c) on Cik, and since j is not linked to k, ((i; a); (j; b); (k; c)) is consistent. Furthermore, (i; a) can be extended to (i; j; k) if there is no constraint between i and k (resp. between i and j). Indeed, (i; a) has a support b in Dj (resp. c in Dk) and this value being arc consistent too, it has a support c in Dk (resp. b in Dj). So, ((i; a); (j; b); (k; c)) is consistent. Consequently, if the constraint network is arc consistent, the only 3-tuples that have to be checked to achieve PIC correspond to the 3-cliques of the constraint graph. 2. However a O(n2d2) data structure is required for the constraint representation. 3. See Section 2 for a definition of n, d, e, c, and g. 211 Debruyne & Bessi`ere jai 0 support AC, RPC, PIC, andMax-RPC delete (i,a) a b jbi 1 support RPC, PIC, and Max-RPC delete (i,a) because its unique support is not path consistent a b k a b ji 2 supports (i, a) is RPC-consistent w.r.t.but PIC and Max-RPC delete this value (C) k ji 2 supports (i, a) is RPC-consistent w.r.t.and PIC-consistent w.r.t. but Max-RPC deletes this value (D) a b k a b l a a b c a b a b a b c a b c C ij C ijC ij (A) (B) A forbidden pair of values. Figure 2: Examples showing the relations between PIC, RPC and Max-RPC. Furthermore, the definition of PIC shows that any constraint network involving less than three variables is path inverse consistent, even though it is not arc consistent. Property 1 A CN is path inverse consistent iff ffl it involves less than three variables, or ffl it is arc consistent and for each value (i; a) in D, for any 3-clique fi; j; kg, (i; a) can be extended to a consistent instantiation of fi; j; kg. This property allows us to see the relations between PIC, RPC and Max-RPC. If a value (i; a) has no support on a constraint Cij, the three local consistencies delete this arc inconsistent value (see Figure 2A). If (i; a) has only one support b in Dj, PIC, RPC, and Max-RPC delete (i; a) because of Cij if ((i; a); (j; b)) is path inconsistent (see Figure 2B). The difference between these three local consistencies appears if (i; a) has at least two supports on Cij. In such a case, (i; a) is restricted path consistent w.r.t. Cij but PIC can delete it if there is a 3-clique fi; j; kg such that all the supports of (i; a) in Dj are path inconsistent because of k (see Figure 2C). So, PIC is more pruningful than RPC. But it 212 Domain Filtering Consistencies often deletes only few additional values because the supports of a value are seldom all path inconsistent because of the same third variable. Max-RPC is far more pruningful since it deletes (i; a) because of Cij if all its supports in Dj are path inconsistent, even if they are not path inconsistent because of the same third variable (see Figure 2D). 5. Pruning Efficiency 5.1 Qualitative Study To compare the pruning efficiency of the local consistencies presented above, we use the transitive relation "stronger" introduced in (Debruyne & Bessi`ere, 1997b). A local consistency LC is stronger than another local consistency LC0 if in any CN in which LC holds, LC0 holds too. Consequently, if LC is stronger than LC0, any algorithm achieving LC deletes at least all the values removed by an algorithm achieving LC0. For instance, since by definition of restricted path consistency RPC is stronger than AC, an RPC algorithm removes at least all the arc inconsistent values. A local consistency LC is strictly stronger than another local consistency LC0 if LC is stronger than LC0 and there is at least one CN in which LC0 holds and LC does not. Theorem 1 Restricted path consistency is strictly stronger than AC. Proof By definition of restricted path consistency, RPC is stronger than arc consistency. Figure 3a shows that there exists a constraint network on which AC holds and RPC does not. Therefore, RPC is strictly stronger than AC. 2 Theorem 2 If k ? k0 *0, k-RPC is strictly stronger than k0-RPC. Proof The proof that k-RPC is stronger than k0-RPC if k ? k0 *0 is trivial. Figure 3g shows that there exists a constraint network on which k0-RPC holds and k-RPC (k ? k0 *0) does not. Therefore, k-RPC is strictly stronger than k0-RPC if k ? k0 *0. 2 Theorem 3 Max-RPC is strictly stronger than k-RPC, 8k *0. Proof The proof that Max-RPC is stronger than k-RPC 8k *0 is trivial. Figure 3g shows that for any k *0 there exists a constraint network on which k-RPC holds and Max-RPC does not. Therefore, Max-RPC is strictly stronger than k-RPC 8k *0. 2 Theorem 4 If jX j *3, path inverse consistency is strictly stronger than restricted path consistency. Proof From property 1, PIC is stronger than AC if jX j *3. Now, consider a value (i; a) having only one support (j; b) on Cij. If PIC holds, for any third variable k, (i; a) can be extended to a consistent instantiation I including fi; j; kg and since b is the only support of (i; a) in Dj, Ij = b. So ((i; a); (j; b)) is path consistent and (i; a) is restricted path consistent w.r.t. Cij. Furthermore, Figure 3b shows that there exists a constraint network on which 213 Debruyne & Bessi`ere RPC holds and PIC does not. Therefore, path inverse consistency is strictly stronger than restricted path consistency if jX j *3. 2 Theorem 5 If jX j *3, max-restricted path consistency is strictly stronger than path inverse consistency. Proof Suppose there is a max-restricted path consistent CN P with a value (i; a) which is not path inverse consistent. Since the CN is max-restricted path consistent, it is also arc consistent by definition of max-restricted path consistency. Thus, because of property 1 we know there exist two variables j and k such that fi; j; kg is a clique in the constraint graph and (i; a) cannot be extended to a consistent instantiation on fi; j; kg. As a result, none of the supports of (i; a) on Cij is path consistent, which contradicts the assumption that the CN P is max-restricted path consistent. Furthermore, Figure 3i shows that there exists a constraint network on which path inverse consistency hold and max-restricted path consistency does not. Therefore, if jX j *3, max-RPC is strictly stronger 2 Theorem 6 Singleton arc consistency is strictly stronger than Max-RPC. Proof Suppose that there exists a CN P with a singleton arc consistent value (i; a) that is not max-restricted path consistent. Let j 2 X be a variable such that (i; a) has no path consistent support in Dj. For each support b of (i; a) in Dj, there exists a variable k such that 6 9c 2 Dk such that Cik(a; c) ^ Cjk(b; c). Therefore, all the values of Dj are arc inconsistent w.r.t. P jDi=fag and (i; a) is not singleton arc consistent. So, SAC is stronger than Max-RPC. Figure 3e shows that there exists a constraint network on which Max-RPC holds and SAC does not. Therefore, SAC is strictly stronger than Max-RPC. 2 Theorem 7 Neighborhood inverse consistency is strictly stronger than max-restricted path consistency. Proof Let (i; a) be any value of a neighborhood inverse consistent CN P . There exists a consistent instantiation I including i and its neighborhood s.t. Ii = a. For any Cij 2 C, Ij is a path consistent support of (i; a). Indeed, let k be any third variable. If k is linked to i, ((i; a); (j; Ij); (k; Ik)) is a consistent instantiation since P is neighborhood inverse consistent. Otherwise, there are two cases: First, if k is not linked to j, ((i; a); (j; Ij); (k; c)) is consistent 8c 2 Dk; Second, if 9Cjk 2 C, there exists a consistent instantiation I0 of j and its neighborhood s.t. I0j = Ij and ((i; a); (j; I0j); (k; I0k)) is consistent. So, (i; a) is max-restricted path consistent. Furthermore, Figure 3d shows that there exists a constraint network on which Max-RPC holds and NIC does not. Therefore, NIC is strictly stronger than Max-RPC. 2 Theorem 8 Strong path consistency is strictly stronger than singleton arc consistency. Proof Consider a problem that is strong path consistent. Any pair of values can be extended to any third variable. Furthermore, since the problem is strong path consistent, it is also arc consistent and a sub-problem obtained by restricting a domain Di to a singleton 214 Domain Filtering Consistencies f(i; a)g can be made arc consistent. The initial problem is therefore singleton arc consistent. Figure 3c shows that there exists a constraint network on which SAC holds and strong PC does not. Therefore, strong PC is strictly stronger than SAC. 2 Theorem 9 Singleton restricted path consistency is strictly stronger than singleton arc consistency. Proof Singleton restricted path consistency is stronger than singleton arc consistency since RPC is stronger than AC. Figure 3d shows that there exists a constraint network on which SAC holds and SRPC does not. Therefore, SRPC is strictly stronger than SAC. 2 The stronger relation does not induce a total ordering. Some local consistencies are incomparable. Theorem 10 1. If jX j *3, path inverse consistency and k-restricted path consistency are incomparable. 2. Neighborhood inverse consistency and singleton arc consistency are incomparable. 3. Neighborhood inverse consistency and strong path consistency are incomparable. 4. Neighborhood inverse consistency and singleton restricted path consistency are incomparable. Proof 1. cf. Figure 3h and Figure 3j. 2. cf. Figure 3d and Figure 3e. 3. cf. Figure 3d and Figure 3e. 4. cf. Figure 3e and Figure 3f. Figure 4 summarizes the relations between the local consistencies. There is an arrow from LC to LC0 iff LC is strictly stronger than LC0. A crossed line between two local consistencies means that they are not comparable w.r.t. the "stronger" relation. When LC is not stronger than LC0 (LC0 is strictly stronger than LC, or LC and LC0 are not comparable), a CN in which LC holds and LC0 does not can be found in Figure 3. Obviously, the stronger relation is transitive. In Figure 4 we omit the transitivity arcs. 215 Debruyne & Bessi`ere AC RPC RPC PIC SAC NIC SAC SRPCStrong PC NIC Strong PC SRPC NIC Strong PC SRPC SRPC NIC SRPC Strong PC SAC Strong PC pair of values.in A B A is not stronger than B (B deletes the value on this A consistent network)forbidden ... The domain of a variable. A Max-RPC NIC NIC SAC SAC RPC 2-RPC 2-RPC PIC k-RPC Max-RPC PIC 2-RPC PIC Max-RPC (c)( a) (b) (e)( d ) (f) (g) ( h ) (j)(i) k-RPC k'-RPC if k'>k>0 Max-RPC NIC k+1 k+1 k+1 k+1 k+1 Figure 3: Some CNs proving the "not stronger" relations between some of the mentioned local consistencies. 216 Domain Filtering Consistencies A B : A and B are incomparable w.r.t. the stronger relation.A B : A is strictly stronger than B. SRPC SAC Max-RPC k-RPC(k>1) RPC AC PIC NICStrong PC Figure 4: Relations between the mentioned local consistencies. 5.2 Experimental Evaluation Figure 4 does not give any quantitative information. A local consistency LC can remove more values than another local consistency LC0 on most of the CNs even though it is incomparable with LC because of some particular CNs. When they are comparable, it does not show if a local consistency is far more pruningful than another or if it performs only few additional value deletions. To have some quantitative information about the pruning efficiency of these local consistencies, we performed an experimental evaluation. The aim of this evaluation is to show how pruningful a local consistency is on random CNs, with a fixed number of variables and values, when the number of constraints and the constraint tightness 217 Debruyne & Bessi`ere 1 .01 .1 .2 .3 .4 .5 .6 .7 .8 .9 1.01 .1 .2 .3 .4 .5 .6 .7 .8 .9 Tightness De ns it y AC RPC PIC 2-RPC Max-RPC SAC Strong PC SRPC NICVariable completability Figure 5: The T0 bounds for random CNs having 40 variables and 15 values in each domain. are changing. We used the random uniform CN generator of (Frost, Bessi`ere, Dechter, & R'egin, 1996) which produces instances according to the Model B (Prosser, 1996). It involves four parameters: n the number of variables, d the common size of the initial domains, p1 the proportion of constraints in the network (the density p1=1 corresponds to the complete graph) and p2 the proportion of forbidden pairs of values in a constraint (the tightness). The generated problems have 40 variables and 15 values in each domain. For each local consistency and each density p1, two particular values of the tightness have been determined. On the one hand, T0(p1) is the tightness such that the local consistency does not delete any value on 50% of the CNs generated with p1 for density. For values of tightness lower than T0(p1), the local consistency seldom deletes many values. On the other hand, Tall(p1) is the tightness such that the local consistency finds the inconsistency of 50% of the CNs generated with density p1. On constraint networks with tighter constraints, the local consistency often removes all the values. For all the mentioned local consistencies, the values T0(p1) 218 Domain Filtering Consistencies .01 .1 .2 .3 .4 .5 .6 .7 .8 .9 1.01 .1 .2 .3 .4 .5 .6 .7 .8 .9 1 De ns it y Tightness AC RPC PIC 2-RPC Max-RPC SAC Strong PC SRPC NICVariable completability Figure 6: The Tall bounds for random CNs having 40 variables and 15 values in each domain. and Tall(p1) for any density p1 are given in Figure 5 and Figure 6 respectively. We also show these bounds for the variable completability filtering which removes all the globally inconsistent values, and thus is the strongest filtering we can have when we limit filtering to the domains. To determine the T0 and Tall bounds, 300 CNs have been generated for each (density, tightness) pair. This explains why the generated problems are relatively small. As already proved theoretically, PIC is stronger than RPC. Their pruning efficiencies are closed. RPC deletes most of the path inverse inconsistent values and is halfway between AC and Max-RPC in terms of pruning efficiency. k-RPC with k ? 1 is incomparable with PIC with regard to the stronger relation. However, Figure 5 and Figure 6 show that 2-RPC is more pruningful than PIC. SAC and strong PC have almost the same pruning efficiency. Their T0 limits merge and their Tall limits show a slight difference. This confirms the similitude between SAC and strong PC pointed out in Section 3. Although SRPC and strong PC are not comparable w.r.t. the stronger relation, SRPC removes is more pruningful than strong PC. As predicted in (van Beek, 1994), these polynomial filterings have more 219 Debruyne & Bessi`ere A C R P C P I C 2-RPC Max- RPC S A C Strong PC SR PC N I CVaria ble completability .0 1 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 1 Tightness Figure 7: The T0 (black points) and Tall (white points) bounds for random CNs having 40 variables, 15 values in each domain, and density 1. difficulties to delete inconsistent values on dense problems with loose constraints. On sparse CNs, the polynomial local consistencies studied are close to variable completability, whereas on very dense CNs, Figure 5 and Figure 6 show a large range of tightnesses between them and variable completability. NIC behaves very differently since on complete constraint networks it corresponds to variable completability. So, on dense CNs, NIC is far more pruningful than the other local consistencies. On CNs generated with a density lower than .28 NIC is less pruningful than SRPC, strong PC and SAC. The more important the propagation through the network is, the closer T0 and Tall are. If a filtering (such as AC) uses a very local property to delete inconsistent values, there is a large set of CNs on which it removes some but not all the values. More pruningful local consistencies consider a more important part of the network to know whether a value is consistent or not. So, they seldom delete few values. On most of the CNs, they do not delete any value, or detect inconsistency: the propagation of the first value deletions often leads to a domain wipe out. 6. Time Efficiency 6.1 Radio Link Frequency Assignment Problems An experimental evaluation has been done on the radio link frequency assignment problems described in (Cabon, de Givry, Lobjois, Schiex, & Warners, 1999), namely the instances of the CELAR4 named Scen01 to Scen11, and the GRAPH instances generated using the GRAPH generator at Delft University named Graph01 to Graph14. In these problems we have to assign frequencies to a set of radio links defined between pairs of sites in order to avoid interferences5. These problems have from 200 to 916 variables and there are 40 values in average in each domain. The constraints are binary and have a cost of violation specified 4. We thanks the Centre d'Electronique de l'Armement (France). 5. See http://www-bia.inra.fr/T/schiex/Doc/CELARE.html for a more detailed presentation of these problems. 220 Domain Filtering Consistencies AC7 RPC2 PIC2 Max-RPC1 SAC1 SRPC1 NIC1 Scen02 0.27 0.7 4.38 6.33 45.5 434.93 10.45 Scen03 0.58 1.55 9.13 14.21 99.49 946.31 26.58 Scen11 0.89 2.53 13.79 25.84 144.3 1362.18 time out Table 2: Cpu time performances on some RLFAP instances on which all the local consistencies studied hold. by a level from 0 to 4. The level 0 corresponds to hard constraints, and levels from 1 to 4 have a decreasing cost of violation. For each problem ScenXX (resp. GraphXX), we call ScenXX.3, ScenXX.2, ScenXX.1 and ScenXX.0 (resp. GraphXX.3, GraphXX.2, GraphXX.1 and GraphXX.0) the problems of satisfaction obtained by considering the problem ScenXX (resp. GraphXX) with only the constraints of level 0 to 3, 0 to 2, 0 to 1, and 0 respectively. In this experimental evaluation, we consider both the cpu time performances and the percentage of values deleted by the local consistencies studied. The algorithms used are AC7 (Bessi`ere, Freuder, & R'egin, 1995), RPC2 (Debruyne & Bessi`ere, 1997a), PIC2 (Debruyne, 2000), Max-RPC1 (Debruyne & Bessi`ere, 1997a), the singleton arc consistency algorithm of (Debruyne & Bessi`ere, 1997b) (SAC1) based on AC6, a SRPC algorithm based on RPC2 (SRPC1), and the NIC algorithm proposed in (Freuder & Elfe, 1996) (NIC1) using FCCBJ (Prosser, 1993) (as in Freuder & Elfe, 1996) with dom+deg dynamic variable ordering heuristic (minimal domain first, in which ties are broken by choosing the variable with the highest degree in the constraint graph Frost & Dechter, 1995; Bessi`ere & R'egin, 1996). All these algorithms have been modified to stop as soon as a domain wipe out occurs. We do not show results on strong PC in this section because on these large problems it requires often more than our 2 hours time out limit. These algorithms have been tested on each ScenXX, Scen XX.X, GraphXX, and GraphXX.X problem using a Sun UltraSparc IIi 440 Mhz. For sake of clarity, we only show the results on some representative problems. 6.1.1 Results on problems on which all the studied local consistencies hold (cf. Table 2) If all the local consistencies studied hold on a constraint network, all the corresponding filtering algorithms are useless. They waste time to check whether the local consistencies hold without deleting any inconsistent value. On these problems, the stronger the local consistency is, the more important is the time wasted. We can see the consequence of the exponential worst case time complexity of NIC1. On most of these problems, NIC1 requires a reasonable cpu time. But as we can see on the problem Scen11, a combinatorial explosion can lead to really prohibitive cpu time for NIC1. 6.1.2 Results on arc inconsistent problems (cf. Table 3) When arc consistency is sufficient to detect the inconsistency of the problem, stronger local consistencies are not always more costly. On Figure 3 we can see that Max-RPC1 has often the best cpu time performances and on Graph06 for example, AC7 is one of the 221 Debruyne & Bessi`ere AC7 RPC2 PIC2 Max-RPC1 SAC1 SRPC1 NIC1 Scen07 0.42 0.43 0.44 0.09 0.59 0.47 1.89 Graph07 0.11 0.14 0.12 0.16 0.24 0.14 1.08 Scen08 0.75 0.48 0.73 0.4 0.52 0.47 time out Graph06 0.48 0.27 0.44 0.26 0.27 0.27 10.13 Table 3: Cpu time performances on some arc inconsistent RLFAP instances. MaxAC7 RPC2 PIC2 RPC1 SAC1 SRPC1 NIC1 Scen06.1 cpu time 0.27 0.48 0.96 2.04 66.32 227.13 time out % of DV 7.88 8.33 17.85 19.7 42.47 42.57 ? Scen09.1 cpu time 0.8 1.52 1.87 5.88 167.85 568.08 318.38 % of DV 22.48 25.79 29.79 31.03 35.86 35.86 31.57 Graph04 cpu time 0.81 2.07 18.65 25.39 2238.13 time out 101.77 % of DV 4.97 6.67 6.95 10.35 18.44 ? 13.14 Graph10 cpu time 1.43 3.32 37.7 51.42 3984.13 time out 2033.39 % of DV 1.43 1.62 1.68 5.42 9.53 ? 7.35 Graph06.1 cpu time 0.39 0.81 0.9 0.8 6.69 3.21 8.54 % of DV 14.96 17.69 100 100 100 100 100 Graph12.1 cpu time 0.73 1.35 2.83 5.41 9.47 32.12 3.97 % of DV 10.42 12.23 15.28 100 100 100 100 Table 4: Cpu time performances and percentages of values deleted by the local consistencies studied (% of DV) on some RLFAP instances. most expensive local consistencies. When enforcing AC requires propagation to find the arc inconsistency of the problem, a stronger local consistency can wipe out a domain more quickly than AC7. On these constraint networks, all the algorithms used have very low cpu time requirements, except NIC1, which can be very expensive on some instances, such as Scen08. 6.1.3 Results on the other problems (cf. Table 4) On many of the RLFAP problems the local consistencies do not delete the same sets of inconsistent values. We can see an important difference between the pruning efficiencies especially on the problems ScenXX.1 and GraphXX.1. Obviously, on most of these problems, the more pruningful the local consistency is, the more important is the time required. We can see this on the problems Scen06.1 and Scen09.1 for example. However, AC7, RPC2, PIC2, and Max-RPC1 have cpu time performances in the same order of magnitude while SAC1, SRPC1, and NIC1 are often far more expensive. 222 Domain Filtering Consistencies This is especially obvious on Graph04 and Graph10. However, it is difficult to say which is the most interesting local consistency on these problems since even if SAC1, and SRPC1 are costly, we can see on Scen06.1 and Graph04 that they can be far more pruningful. These problems highlight that NIC1 is not very stable. It sometimes shows good performances, but an exponential explosion can lead to a prohibitive cost on some instances. When NIC1 requires a reasonable time, its pruning efficiency is closer to the one of MaxRPC1 than to the one of SAC1. These results confirm that if the neighborhoods of the variables are not small, NIC1 can be really prohibitive. On Graph06.1, PIC2 (and obviously the algorithms enforcing a stronger local consistency) finds the inconsistency of the problem whereas AC7, and RPC2 remove only a part of the inconsistent values. We can see a similar behavior on Graph12.1 where Max-RPC1 wipes out a domain whereas AC7, RPC2 and PIC2 do not find the inconsistency of the problem. On these instances, Max-RPC1 is the best choice. 6.2 Randomly Generated Problems The random uniform CN generator of section 5.2 is used to compare the cpu time required to enforce the local consistencies. We have to point out that NIC has not been designed to be used on uniform CNs but to adapt filtering effort to the degree of the variables in the constraint graph. So, NIC would have better performances on non-uniform CNs than those presented in this section. The generated problems have 200 variables and 30 values in each initial domain. Figure 8 shows the results on CNs with density of .02. These CNs are relatively sparse since the variables have four neighbors on average. Figure 9 presents performances at density .15 (the variables have 30 neighbors on average). Because of the set of parameters, there are no flawed variables (MacIntyre, Prosser, Smith, & Walsh, 1998) in the generated problems.6 In addition to the algorithms of the previous section, we use a strong path consistency algorithm based on PC8 (Chmeiss & J'egou, 1996) and AC6. This algorithm stops as soon as a domain wipe out occurs or as soon as a constraint no longer allows any pair of values. In addition to the percentage of deleted values and cpu time performances, Figure 8 and Figure 9 show the cpu time to number of deleted values ratio for each tightness where the local consistency removes at least one value on average. For each tightness, 50 instances were generated. Figure 8 and Figure 9 show mean values obtained on a Pentium II-266 Mhz with 32 Mb of memory under Linux. As observed in (Gent, MacIntyre, Prosser, Shaw, & Walsh, 1997) for arc consistency, the filtering algorithms tested have a complexity peak. For low values of the tightness, they easily prove that the values are locally consistent, and when constraints are very tight, they quickly wipe out a domain. Each local consistency has a phase transition where most of the hardest problems for an algorithm achieving this local consistency tend to occur. 6.3 Experiments on Sparse CNs Even on sparse CNs (see Figure 8), the cpu time results are so different between the algorithms (7h 48min for strong PC at its peak when AC7 requires at most .22 seconds on average) that a logarithmic scale has to be used. Strong PC is really prohibitive, even for 6. In Section 5.2,the tightness reaching 1, there was obviously flawed variables for some sets of parameters. 223 Debruyne & Bessi`ere low values of tightness. SRPC and SAC have bad cpu time to number of deleted values ratios, except SAC on CNs having very tight constraints because the SAC algorithm used is based on AC6 which can be more efficient than AC7 on such problems. On these sparse CNs, NIC has often better cpu time performances than SAC but it does not remove more values than Max-RPC. Consequently, NIC has a bad cpu time to number of deleted values ratio. Unlike strong PC, SRPC, SAC, and NIC, the cpu time requirements of AC7, PIC2, RPC2 and Max-RPC are of the same order of magnitude. The cpu time to number of deleted values ratios of these four last filterings are also very close, with a little advantage for PIC2. Although PIC is stronger than RPC, PIC2 can be less expensive than RPC2 on sparse CNs. If there are few 3-cliques in the constraint graph, PIC2 does not require far more cpu time than AC7 whereas RPC2 is about two times as expensive as AC7 since it looks for two supports for each value on each constraint. 6.4 Experiments on more Dense CNs On more dense CNs (see Figure 9), the complexity peaks of AC7, RPC2, PIC2, and MaxRPC stay close to each other. PIC2 is less worthwhile since it deletes few additional values compared to RPC2 while its cpu time requirements are close to those of Max-RPC. MaxRPC has one of the best cpu time to number of deleted values ratios. As soon as RPC leads to a domain wipe out, the cpu time performances of SRPC and RPC2 merge. Indeed, the SRPC algorithm used enforces RPC2 before checking the restricted path consistency of the sub-problems P jDi=fag for each (i; a) 2 D. If all the values of a domain are restricted path inconsistent, the RPC preprocessing finds the global inconsistency of the problem and the SRPC algorithm stops. SRPC is less expensive than strong PC although it is more pruningful. These two filterings remain the most expensive. NIC is the most pruningful local consistency on these CNs. Hence, on a large range of tightnesses, NIC has the best cpu time to number of deleted values ratio. However, on some instances, NIC cannot avoid the combinatorial explosion. Although NIC requires "only" fifteen minutes on average at tightness .52, more than two hours are required on some instances. It is conceivable that instances on which NIC requires far more cpu time exist for this set of parameters. Obviously, the set of CNs on which NIC is prohibitive grows when the density increases. The results on SAC have a lower standard deviation. SAC never requires more than fifty two minutes on the problems generated for these experiments. 6.5 Discussion What can we conclude from these results? Strong PC is by far the least interesting filtering technique. Compared to SAC, which removes most of the strong path inconsistent values, strong PC is really prohibitive.7 Achieving SAC or SRPC is costly as long as these two local consistencies do not delete any value. Obviously, although SAC and SRPC are more expensive than Max-RPC on almost all the generated problems, we cannot say that it is better to use Max-RPC. Indeed, at density .15 for example, Max-RPC is useless for 7. We can point out that when the path consistency of a constraint can be expressed without explicitly storing the set of forbidden tuples, path consistency can be used (e.g., temporal networks Allen, 1983, constraint networks Smith, 1992). 224 Domain Filtering Consistencies 1E-3 1E-2 1E-1 1E+0 1E+1 1E+2 1E+3 1E+5 1E-7 1E-6 1E-5 1E-4 1E-3 1E-2 1E-1 1E+0 1E+1 1E+2 1 5 10 15 20 25 30 3 5 40 45 50 55 60 6 5 70 75 8 0 85 90 9 5 9 9 cpu time (in sec.) Tightness 1 5 10 1 5 20 25 30 35 40 4 5 50 5 5 60 65 70 75 80 8 5 90 95 9 9 Tightness0 100 Percentage of values deleted 1 5 10 15 20 25 30 3 5 40 45 50 55 60 6 5 70 75 8 0 85 90 9 5 99 Tightness cpu time to number of deleted values ratio 75 80 85 90 95 1E-5 1E-4 1E-3 1E-2 1E-1 AC7 RPC2 PIC2 Max-RPC SAC SRPC Strong PC NIC A C 7 RPC2PIC2 Max-RPC SAC NIC n=200, d=30, and p1=.02 1E+4 Strong PC SRPC 7h48min 16min15sec 2min36sec 9.33sec 0.36sec 0.22sec AC7 RPC2 PIC2 Max-RPC Strong PCSAC SRPC NIC 0.24sec 0.37sec Figure 8: Experimental evaluation on random CNs with n=200, d=30, and p1=.02. 225 Debruyne & Bessi`ere 12h40min 1E-3 1E-2 1E-1 1E+0 1E+1 1E+2 1E+3 1E+5 1 5 1 0 15 2 0 2 5 30 3 5 40 45 5 0 5 5 60 6 5 70 75 80 8 5 90 9 5 0 100 1E+2 9 9 cpu time (in sec.) Percentage of values deleted Tightness 1 5 10 1 5 20 25 3 0 35 40 45 50 55 60 65 70 7 5 8 0 85 90 95 99 Tightness Tightness cpu time to number of deleted values ratio 1E-7 1E-6 1E-5 1E-4 1E-3 1E-2 1E-1 1E+0 1E+1 1 5 10 15 20 25 30 3 5 40 45 50 55 60 6 5 70 75 8 0 85 90 9 5 99 6 5 70 75 80 85 90 NIC Max-RPC PIC2 SAC SRPC RPC2 Strong PC AC7 1E-2 1E-3 1E-5 1E-6 1E-4 NIC Max-RPC PIC2RPC2 AC7 SAC SRPC n=200, d=30, and p1=.15 1E+4 Strong PC 3h53min 39min43sec 15min21sec 8.63sec 6.25sec 2.44sec 1.11sec AC7 RPC2 PIC2 Max-RPC Strong PCSAC SRPC NIC Figure 9: Experimental evaluation on random CNs with n=200, d=30, and p1=.15. 226 Domain Filtering Consistencies tightnesses lower than .63 since it does not delete any value, while for SRPC the limit is .57 of tightness. Furthermore, for singleton consistencies we can argue that the algorithm used to achieve them is not optimal. An algorithm reusing part of the filtering performed on P jDi=fag to process other sub-problems P jDj=fbg, ((i; a) and (j; b) belonging to D) would improve cpu time performances. However, the cpu time to number of deleted values ratios of SAC and SRPC algorithms are often among the worst ones, especially on sparse CNs. SAC and SRPC are so expensive that it is hardly likely that enhancements of these algorithms could lead them to be the most worthwhile filterings. On sparse uniform CNs, NIC is not the best choice. Compared to Max-RPC, it does not delete enough values to offset the additional cpu time cost. Furthermore, NIC cannot be used on dense CNs since its cpu time requirements become greater than those of a search algorithm. So, NIC has to be used only on "relatively" dense CNs, as those of Figure 9 on which NIC is worthwhile on average (although on some instances a combinatorial explosion cannot be avoided). On very dense CNs, the worst case time complexity of Max-RPC and PIC2 is close to the one of the best path consistency algorithm (O(en + ed2 + cd3) against O(n3d3)). However, the experiments underline that achieving Max-RPC and PIC2 is far less expensive in practice. Compared to RPC2 and Max-RPC, PIC2 is not a good solution in-between. The cpu time to number of deleted values ratios of RPC2 and Max-RPC are better than the one of PIC2 (except on very sparse CNs on which PIC2 can be less expensive than RPC2). Indeed, PIC2 deletes only few additional values compared to RPC2, while its cpu time performances are close to those of Max-RPC. Cpu time performances are even more essential when the aim is to maintain a local consistency during search. Maintaining a local consistency during search requires to repeatedly propagate the choice of a value for a variable (namely the restriction of a domain to a singleton) or the refutation of a value. To be worthwhile, a local consistency has to require less time to detect that a branch of the search tree does not lead to a solution than a search algorithm to explore this branch. So, maintaining a local consistency during search can outperform MAC on hard problems only if this local consistency is more pruningful than AC while requiring only a little additional cpu time. With regard to this criterion, we can discard strong PC, SAC, SRPC, and NIC on dense CNs because they are too expensive. It is conceivable that we can find instances on which maintaining these consistencies during search outperforms MAC, but the more expensive the maintained local consistency is, the more seldom the problems on which MAC is outperformed will be. On sparse CNs, NIC is not prohibitive, but it deletes only few additional values compared to Max-RPC and it has therefore a bad cpu time to number of deleted values ratio. Finally, The most promising local consistencies are RPC and Max-RPC. If we exclude arc consistency, RPC is the least expensive local consistency we studied. Furthermore, the RPC algorithms delete most of the path inverse inconsistent values. Although Max-RPC is far more pruningful than arc consistency, experiments show that in practice, Max-RPC has very good cpu time results. Therefore, it seems very likely that maintaining RPC or Max-RPC during search could outperform MAC on very hard problems. To confirm these results, an algorithm called Quick that maintains an adaptation of Max-RPC has been compared to MAC. The results of these experiments (Debruyne, 1999) show that Quick has better cpu time performances than MAC on large and hard randomly generated CNs that are relatively sparse. More interestingly, Quick has a more impor227 Debruyne & Bessi`ere tant stability than MAC (the cpu time performances of Quick have a very low standard deviation). It would be very interesting to propose efficient algorithms that maintain the local consistencies studied in this paper and to compare these algorithms. Such a study would allow us to know whether during search, the more advantageous local consistencies remain RPC and Max-RPC as during a preprocessing step. First results on the effect of maintaining SAC during search are given in (Prosser, Stergiou, & Walsh, 2000). 7. Conclusion In this paper we extended the idea of restricted path consistency to k-RPC and MaxRPC, which are more pruningful local consistencies. We proposed a new class of local consistencies called singleton consistencies. We studied these new local consistencies and the other local consistencies that alike can be used on large CNs while removing more values than arc consistency. We showed some relations between them and we compared both theoretically and experimentally their pruning and time efficiencies. The most pruningful are neighborhood inverse consistency and singleton restricted path consistency. However, SRPC is expensive in time and the exponential worst case time complexity of NIC makes it unusable on dense CNs. If we are looking for a local consistency that would advantageously be maintained during search, RPC and Max RPC seem to be the most promising local consistencies. Indeed, they are relatively inexpensive and far more pruningful than arc consistency. 8. Acknowledgements We would like to thank Toby Walsh for his suggestions for improving the presentation of the figures in Section 5. References Allen, J. (1983). Maintaining Knowledge about Temporal Intervals. Communications of the ACM, 26(11), 832-843. Bacchus, F., & van Run, P. (1995). Dynamic variable ordering in csps. In Proceedings of CP-95, Cassis, France, pp. 258-275. Berlandier, P. (1995). Improving domain filtering using restricted path consistency. In Proceedings of IEEE CAIA-95. Bessi`ere, C., Freuder, E., & R'egin, J. (1995). Using inference to reduce arc-consistency computation. In Proceedings of IJCAI-95, Montr'eal, Canada, pp. 592-598. Bessi`ere, C., Freuder, E., & R'egin, J. (1999). Using constraint metaknowledge to reduce arc consistency computation. Artificial Intelligence, 107(1), 125-148. Bessi`ere, C., & R'egin, J. (1996). MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems. In Proceedings of CP-96, Cambridge MA, pp. 61-75. 228 Domain Filtering Consistencies Cabon, C., de Givry, S., Lobjois, L., Schiex, T., & Warners, J. (1999). Radio link frequency assignment benchmarks. CONSTRAINTS, 4(1), 79-89. Cheeseman, P., Kanefsky, B., & Taylor, W. (1991). Where the really hard problems are. In Proceedings of IJCAI-91, Sydney, Australia, pp. 294-299. Chmeiss, A., & J'egou, P. (1996). Two new constraint propagation algorithms requiring small space complexity. In Proceedings of IEEE ICTAI-96, Toulouse, France, pp. 286-289. Debruyne, R. (1999). A strong local consistency for constraint satisfaction. In Proceedings of IEEE ICTAI-99, Chicago IL, pp. 202-209. Debruyne, R. (2000). A property of path inverse consistency leading to an optimal algorithm. In Proceedings of ECAI-00, Berlin, Germany, pp. 88-92. Debruyne, R., & Bessi`ere, C. (1997a). From restricted path consistency to max-restricted path consistency. In Proceedings of CP-97, Linz, Austria, pp. 312-326. Debruyne, R., & Bessi`ere, C. (1997b). Some practicable filtering techniques for the constraint satisfaction problem. In Proceedings of IJCAI-97, Nagoya, Japan, pp. 412-417. Dechter, R., & Meiri, I. (1994). Experimental evaluation of preprocessing algorithms for constraint satisfaction problems. Artificial Intelligence, 68, 211-241. Dechter, R., & Pearl, J. (1988). Network-based heuristics for constraint-satisfaction problems. Artificial Intelligence, 34, 1-38. Freuder, E. (1982). A sufficient condition for backtrack-free search. Journal of the ACM, 29(1), 24-32. Freuder, E. (1985). A sufficient condition for backtrack-bounded search. Journal of the ACM, 32(4), 755-761. Freuder, E. (1991). Completable representations of constraint satisfaction problems. In Proceedings of KR-91, Cambridge MA, pp. 186-195. Freuder, E., & Elfe, C. (1996). Neighborhood inverse consistency preprocessing. In Proceedings of AAAI-96, Portland OR, pp. 202-208. Frost, D., Bessi`ere, C., Dechter, R., & R'egin, J. (1996). Random uniform csp generators. In http://www.ics.uci.edu/~ frost/csp/generatotr.html. Frost, D., & Dechter, R. (1995). Look-ahead value ordering for constraint satisfaction problems. In Proceedings of IJCAI-95, Montr'eal, Canada, pp. 572-578. Gaschnig, J. (1974). A constraint satisfaction method for inference making. In Proceedings of the 12th Annual Allerton Conf. Circuit System Theory, U.I.L., Urbana-Champaign IL, pp. 866-874. 229 Debruyne & Bessi`ere Gent, I., MacIntyre, E., Prosser, P., Shaw, P., & Walsh, T. (1997). The constrainedness of arc consistency. In Proceedings of CP-97, Linz, Austria, pp. 327-340. Golomb, S., & Baumert, I. (1965). Backtrack programming. Journal of the ACM, 12(4), 516-524. Grant, S., & Smith, B. (1996). The phase transition behaviour of maintaining arc consistency. In Proceedings of ECAI-96, Budapest, Hungary, pp. 175-179. Haralick, R., & Elliott, G. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14, 263-313. Kumar, V. (1992). Algorithms for constraint satisfaction problems: A survey. AI Magazine, 13(1), 32-44. MacIntyre, E., Prosser, P., Smith, B., & Walsh, T. (1998). Random constraint satisfaction: theory meets practice. In Proceedings of CP-98, Pisa, Italy, Vol. 19, pp. 325-339. McGregor, J. (1979). Relational consistency algorithms and their application in finding subgraph and graph isomorphisms. Information Sciences, 19, 229-250. Meseguer, P. (1989). Constraint satisfaction problems: An overview. AICOM, 2, 3-17. Nadel, B. (1988). Tree search and arc consistency in constraint satisfaction algorithms. in L. Kanal and V. Kumar, editors, Search in Artificial Intelligence, Springer-Verlag, 287-342. Prosser, P. (1993). Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence, 9(3), 268-299. Prosser, P. (1996). An empirical study of phase transition in binary constraint satisfaction problems. Artificial Intelligence, 81, 81-109. Prosser, P., Stergiou, K., & Walsh, T. (2000). Singleton consistencies. In Proceedings of CP-00, Singapore, pp. 353-368. Sabin, D., & Freuder, E. (1994). Contradicting conventional wisdom in constraint satisfaction. In Proceedings of ECAI-94, Amsterdam, Netherlands. Schiex, T., R'egin, J., Gaspin, C., & Verfaillie, G. (1996). Lazy arc consistency. In Proceedings of AAAI-96, Portland OR, pp. 216-221. Singh, M. (1995). Path consistency revisited. In Proceedings of IEEE ICTAI-95, Washington D.C. Smith, B. (1992). How to Solve the Zebra Problem, or Path Consistency the Easy Way. In Proceedings of ECAI-92, pp. 36-37. Tsang, E. (1993). Foundations of Constraint Satisfaction. London, Academic Press. van Beek, P. (1994). On the inherent level of local consistency in constraint networks. In Proceedings of AAAI-94, Seattle WA, pp. 368-373. 230