Constraint Satisfaction over Connected Row Convex Constraints

1 Introduction

Constraint satisfaction techniques have been found use­ ful in many areas such as Operations Research, hard­ ware design , robotics, knowledge bases, and temporal resaoning to name a few. Some applications require to find one or all solutions, in which case consistency tech­ niques such arc and path consistency are instrumental in reducing the size of the search space. Other applications require to put the graph of constraints in minimal form, e.g., to remove redundant information.

Increasing attention has been devoted recently to the study of special classes of constraints or contraint graphs . These studies are motivated both by practical consider­ ations (e.g. , constraint languages are based on a set of primitive constraints) and by theoretical considerations, since stronger results and more efficient algorithms can be obtained by exploiting special properties.

This paper considers the class of connected row con­ vex ( CRC) constraints. CRC constraints were moti­ vated by van Beek's row convex constraints, their prop­ erties, and their applications to various tasks in arti­ ficial intelligence [van Beek and Dechter , 1995]. The

Pascal Van Hentenryck

Brown University Box 1910 Providence, RI 02912, USA pvh@cs.brown.edu

class of CRC constraints include many constraints such as ax + by + c :S 0, ax + by + c 2: 0, axy + b :S 0, axy+ b 2: 0, af(x) +by + c :S 0, and af(x) +by +c 2: 0, where a, b, c are rationals and f( x) is a function whose derivative does not change sign in the considered do­ main as well as conjunctions of these constraints, some of which being non-monotone. We show that, contrary to row convex constraints, CRC constraints are closed un­ der intersection, composition, and transposition, the ba­ sic operations of path-consistency algorithms. We then propose a generic path-consistency algorithm PC-GEN which mimics the generic arc-consistency algorithm AC5 and we show that it can be instantiated to produce a path-consistency algorithm running in time O(n 3 d 2 ) and in space O(n 2 d) for CRC constraints. Finally, we show that finding a solution to a path-consistent graph of CRC constraints can be done in 0( n 2 ) time.

The rest of the paper is organized as follows. Section 2 introduces the necessary background on Constraint Sat­ isfaction Problems (CSPs) and Section 3 discusses re­ lated work. Section 4 introduces CRC constraints and studies their properties Section 5 presents PC-G EN and Section 6 instantiates it for CRC constraints. Section 7 concludes the paper.

2 Background

In this paper, variables are represented by the natural numbers 1, ... , n. Each variable i has an associated fi­ nite domain Di. All constraints are binary and relate two distinct variables. If i and j are variables ( i < j), we assume, for simplicity, that there is at most one con­ straint relating them, denoted by Cij. A constraint Cij denotes a set of couples ( Cij ~ Di x Dj ). The fact that ( v, w) E Cij is also be denoted by Cij ( v, w). We denote by D the union of all domains and by d the size of the largest domain. We assume the existence of a total or­ dering over D. Following Montanari [1974], a constraint Cij will also be seen as a (0,1)-matrix with I Di I rows and I Dj I columns. Rows and columns are ordered ac­ cording to the underlying order over D. A 1 (resp. 0) at position (v, w) in the matrix means (v, w) E Cij (resp . (v ,w) rf. Cij)· To simplify the presentation, each domain Di is also represented by a (pseudo-binary) constraint C;i such that C;;(v, v) holds iff v ED;. Domain Di and constraint C;; can be used in an interchangeable way.

Consistency algorithms generally work on the graph representation of the CSP. We associate a graph G to a CSP in the following way. G has a node i and an arc (i, i) for each variable i . The constraint associated to arc ( i, i) is C;;. For each constraint C;j relating vari­ ables i and j ( i < j), G has two directed arcs, ( i , j) and (j, i). The constraint associated to arc ( i, j) is C;j and the constraint associated to (j, i) is Cj;, which is the transposition of C;j. The graph is thus defined by the nodes, the arcs, and their associated constraints . We use arc( G) and node( G) to denote the set of arcs and the set of nodes of graph G. A CSP uniquely defines a graph and vice versa. The tuple ( vl' ... 'Vn) E nn is a solution of G if C;j(v;,vj) holds for all (i,j) E arc(G) . Two graphs G and G' are equivalent if G and G' have the same solutions.

Let us review some of the basics in the area of path consistency. A tuple (v; 0 , v;m) is path-consistent for path (io, ... ,im) wrt G if3v; 1 , ··· ,v;m_ 1 such that v;k E D;k (1::; k < m) and C;k;k+ 1 (v;k,v;k+J (0::; k < m) . The path p = (i0 , ... , im) in G is path-consistent wrt G if for all Vio E D;o and Vim E D;m with cioim ( Vio' V;m), (v; 0 , v;m) is path-consistent for p wrt G. A graph G is path consistent if for all paths p in G, p is path consis­ tent wrt G. Montanari l1974] showed that a complete graph is path consistent iff all paths of length two are path-consistent . Typically, path-consistency algorithms work on complete graphs, and an incomplete graph can be easily transformed into a complete graph by adding TRUE constraints . The objective of a path-consistency algorithm is thus, given a complete graph G, to compute new constraints which are path consistent and have the same solutions as G. Path-consistency algorithms are generally defined in terms of interesection and composi­ tion of the matrix representation defined as

A graph G is minimal if, for all i, j E node( G) and for all v, w E D, C;j(v, w) implies that (v, w) is part of some solution of G. A graph G is decomposable if, for all v; 1 ··· v;k satisfying all the constraints relating nodes i1 ... ik (1 ::; k < n) and for any new node ik+l, there exists v;k+ 1 such that V; 1 ... v;k, v;k+i satisfy all the constraints relating nodes i1 ... ik, ik+l· A decomposable graph is also called strongly n-consistent [Freuder, 1982]. Decomposable graphs have thus the property that any consistent instantiation of some variables can be ex­ tended to a solution without backtracking. A decompos­ able graph is of course minimal. In a minimal graph, it is not possible to prune further the constraints without removing solutions.

3 Related Work

This research was motivated by van Beek's result on row convex constraint. A constraint C;j is row convex if, in each row of its matrix representation, all the ones are consecutive. Van Beek and Dechter [1995] show that , when the constraints of a path-consistent graph are row convex (or can be made row convex by permutation of values in the domain) , then the graph is minimal and decomposable. One can thus compute a solution with­ out backtrackin§ in O(n 2 d). Solving the CSP can then be done in O(n d 3 ), the time complexity of the PC al­ gorithm. Unfortunately, row convex constraints are not closed under composition and intersection. As a conse­ quence, no conclusion can be drawn a priori for a graph of row convex constraints, since its path consistent sub­ graph may or may not be row convex. CRC constraints remove this problem, since a graph of CRC constraints, after application of a path consistency algorithm, is still CRC and is thus minimal and decomposable.

In [1995], Jeavons and Cooper identify the class of max-closed constraints that can be solved in polynomial time (O(n 4 d 4 ) for binary constraints) . Our class ofCRC constraints, which can be solved in O(n 3 d 2 ), intersects with max-closed constraints, but is not a subset .

The idea of row convexity has also been exploited in the context of continuous constraints [Haroud and Falt­ ings, 1996] . They start from the result that, when con­ straints are convex and binary, path-consistency is suffi­ cient to ensure decomposability. They show that for con­ tinous domain, this result can be generalized to ternary and n-ary constraints using some other notion of consis­ tency ( (3,2)-relational consistency).

The class of CRC constraint is also related to dis­ crete temporal reasoning [van Beek, 1992b]. Valdes­ Peres [Valdes-Perez, 1987] shows that path-consistency algorithms find the minimal network for a subclass of Allen's interval algebra [Allen, 1983] . Such a result has also been proposed in the context of point algebra [Vilain and Kautz, 1986; van Beek, 1989].

Montanari [Montanari, 1974] already shows that a path-consistent tree or distributive networks are min­ imal. He also shows that path consistency of (total) monotone constraints produces a decomposable network. Note that CRC constraints are not distributive and gen­ eralize the total monotone functions of Montanari.

Finally, recall that best path-consistency algorithms [Chmeiss, 1996; Han and Lee, 1988; Mohr and Hender­ son, 1986; Singh, 1995] run in time O(n 3 d 3 ) and in space O(n 3 d 2 ) (PC-6). These algorithms do not take advan­ tage of properties of the constraints. A generic arc­ consistency algorithm AC-5 has been proposed in [Van Hentenryck et al., 1992] and it can be instantiated to pro­ duce linear algorithms for different classes of constraints such as functional and monotone constraints.

4 Connected Row Convex Constraints

Row convex constraints exhibits two problems during path-consistency algorithms. First, when a row convex constraint is composed of disjoint blocks of 1s, its com­ position with another row convex constraint may not be row convex. Second, even if disjoint blocks are forbidden, intersection may create empty rows and columns and thus disjoint blocks. Here is an illustration of these two

CRC constraints avoid both problems. Informally, a constraint is CRC if, after removing the empty rows, it is row convex and connected (two successive rows either intersect or are consecutive).

Definition 1 The reduced form of a constraint C;j, de­ noted by C;*j, is obtained by removing all the empty rows and columns in its matrix representation. The domain of i through the constraint C;j, denoted by D; ( C;j), is the set {v ED l3w: (v,w) E C;j}·

Definition 2 Let C;j be a row convex constraint and v E D;(C;j) · The image of v in C;j is the set {w I (v, w) E C;*j}. Because of the row convexity of C;j, this set is represented as an interval [ Wr, wm] (over the do­ main Dj(Cj;)) and we denote w1 and Wm by min(C;j, v) and max( C;j, v) respectively. We also denote by succ( w) and pred( w) the successor and the predecessor of w in Dj(Cj;).

Definition 3 A row convex constraint C;j is connected ifthe images [a, b] and [a', b'] of two consecutive rows in C;*j is such that b' 2: pred( a) 1\ a' :S succ( b).

Definition 4 A constraint C;j is connected row convex (CRC) if C;*j and CJ; are both row convex and connected.

We assume that C;j is always the transposition of Cji· Notice that CRC constraints are not necessarily row con­ vex (because of empty rows) and that row convex con­ straints are not necessarily CRC (not connected rows).

The main result of this section is the fact that CRC constraints are closed under composition, intersection and transposition.

Lemma 1 The deletion of rows and columns in a CRC constraint produces a CRC constraint.

Connectivity in Lemma 1 can be proven by showing that all the columns between two non-connnected rows are necessarily empty and must thus be deleted when con­ sidering the connectivity property.

Lemma 2 Let C;j be a CRC constraint. Let v1 , v, v2 be in D; ( C;j) such that v 1 < v < v2 and their respective images are [ar,br], [a,b] and [a2,b2] in C;j.

Theorem 5 The intersection and composition of two CRC constraints and the transposition of a CRC con­ straint are CRC constraints.

Proof (Sketch) Transposition is obvious. For intersec­ tion and composition (C =An B or C = A.B), delete the empty rows and columns in the operands to give A+ and B+. By Lemma 1, it is sufficient to show that c+ = A+ n B+ or c+ = A+ .B+ are CRC. Row convex­ ity is obvious for intersection and results from Lemma 2 for composition. Connectivity can be proven by showing that all the columns between two non-connnected rows are necessarily empty and must thus be deleted when considering the connectivity property. 0

Theorem 6 Let G be composed of CRC constraints. The application of a path-consistency algorithm to G produces a minimal and decomposable graph.

5 PC-GEN: Generic Path Consistency

We now present a path-consistency algorithm for CRC constraints. We proceed in two steps. We first present a generic path-consistency algorithm PC-G EN which is parametrized in a way similar to AC-5. We then instan­ tiate PC-GEN to CRC constraints.

procedure PRUNE(in b.,i,j) Pre: i,j E node(G). Post: C;j = C;j 0 \ {(v,w) I (v,w) E b.}, Cji = Cji 0 \ {(w,v) I (v,w) E b.}. procedure INITQUEUE(out Q) Post: Q = {}. function EMPTYQUEUE(in Q): Boolean Post: EMPTYQUEUE ¢> (Q = {} ). procedure DEQUEUE(inout Q, out i, k,j, (v,u)) Post: (i, k, j, (v, u)) E Qo and Q = Qo \ { (i, k, j, (v, u)) }. procedure ENQUEUE(i, j, b., inout Q) Pre: b. ~ C;j. Post: Q = Qo u{(i,j,k,(v,w)) IkE node(G) and j f. k and (v,w) E b.}. u{(j,i,k,(w,v)) IkE node(G) and j f. if. k and (v,w) E b.}. Let PCikj(v,w) = 3u: (v,u) E C;k and (u,w) E Ckj· PCikj(v, w) = 3u: ((v, u) E C;k V (i, k,j, (v, u)) E Q) and ((u,w) E Ckj V (j,k,i,(w,u)) E Q) procedure PATHCONs(in i, k, j, out b.) Pre: i,k,j E node(G). Post: b.= {(v,w) E C; 1 l..,pcikj(v,w)}. procedure LOCALPATHCONS(in i, k, j,(v, u), out b.) Pre: i,k,j E node(G), and (v,u) ~ Cik· Post: b.1 C b. C b.2, with b.1; {(v~w') E C;j I (u,w') E Ci']it and ..,pcikj(v,w')}. b.2 = {(v',w') E C;j l..,pcikj(v',w')}.

The specification of the main operations in PC-GEN are given in Figure 1. In all specifications, a parameter p subscripted with 0 (p0 ) represents the value of p at call time and Cfjit is the original set of constraint tuples between i and j. This justifies the restriction i :S j in line 2 of PC-GEN. As is traditional, PC-GEN uses a queue to drive the algorithm. Procedure ENQUEUE is required to take O(s) time, where sis the number of new elements to insert in the queue, and procedure DEQUEUE must take constant time. The deletion of tuples is performed by procedure PRUNE, which removes tuple (v, w) from C;j, and (w, v) from Cji · Hence, (v, w) E C;j {:::} (w, v) E Cji is an invariant of the algorithm.

PC-GEN is parametrized by two procedures, PATH­ CoNs and LOCALPATHCONS whose implementations are left open. Procedure PATHCONS computes the set 6. of tuples in C;j which are not path consistent for the path (i, k,j). Because of the relationship between C;j and Cji, 6. is also the set of tuples (in reverse order) of Cji that are not path consistent for path (j, k, i).

Procedure LOCALPATHCONS returns in 6. a set of tuples of C;j that are not path consistent for ( i, k, j) after the tuple (v, u) has been removed from the con­ straint C;k. The set 6. is also the set of tuples (in reverse order) of Cji that are not path consistent in path (j, k, i) after tuple (u, v) has been removed from cki·

The size of 6. computed by LOCALPATHCONS can vary. The set 6.1 contains the tuples in C;j that be­ come path inconsistent for ( i, k, j) due to the removal of the tuple (v, u) from C;k. Specifically, a tuple (v, w') is included in 6. 1 if u was a support (i.e., ( u, w') E C1't) and (v, w') is not supported anymore. In some cases, it is possible, but not always desirable, to prune a larger set of tuples. As an extreme case, 6.2 prunes all tuples in C;j which are not path inconsistent wrt ( i, k, j) at call time, regardless of whether they can be supported by (v, u). In fact, the specifications can be made even less restrictive by replacing PCikj by PC:kj in the def­ inition of 6. in PATHCONS , and in the definition of 6. 1 in LOCALPATHCONS. Our instantiation of PC-GEN to CRC constraints uses this flexibility to improve the time complexity of traditional path-consistency algorithms.

PC-GEN is depicted in Figure 2 and mimics AC-5 . In the loop on lines 2-7, procedure PATHCONS identifies the path-inconsistent tuples with respect to each path of length two. The inconsistent tuples are enqueued and processed in the second loop , on lines 8-14, where pro­ cedure LOCALPATHCONS is used to prune tuples of C;j which become inconsistent after the removal of a tuple from Cik· The removal of the tuple (v, w) in C;i and (w, v) in Cji induces to reconsider all length-two paths involving either ( i, j) or (j, i) as the first or as the second arc. It is however unnecessary to explicitly consider the involvement as a second arc (in the ENQUEUE procedure) since LocALPATHCoNs(i,j, k, . . . ) will cover both paths (i,j,k) and (k,j,i), and LOCALPATHCONS(j,i,k, ... ) will cover paths (j,i,k) and (k,i,j) .

It can be shown that PC-GEN is correct and that it enqueues and dequeues at most O(n 3 d 2 ) elements.

Theorem 7 Given a time complexity of O(d 2 ) for pro­ cedure PATHCONS and a time complexity of 0(6.) for procedure LOCALPATHCONS, the time complexity of al­ gorithm PC-GEN is bounded by O(n 3 d 2 ).

PC-GEN can be instantiated for general constraints to produce a path-consistency algoritm with a time com­ plexity of O(n 3 d 3 ) and a space complexity of O(n 3 d 2 ). We now turn to its instantiation for CRC constraints.

6 PC-GEN for CRC Constraints

CRC constraints can be represented in space 0( d) as shown in Figure 3. It is necessary to keep a de­ scription of D; ( C;j), since row convexity is only en­ forced on the reduced form. Figure 3 also spec­ ifies the operations on CRC constraints which are all implemented in constant time. For instance, EMPTYSUPPORT(v,w,i,k,j) can be implemented by b' 2: a 1\ a':::; b with a =MIN(v, i, k), b =MAX(v, i, k), a' =MIN(w,j, k), and b' =MAX(w,j, k).

. procedure PATHCONs(in i, k,j, out~) begin 1 ~ := 0; 2 for each v E D;(Cij) do 3 begin 4 LOCALPATHCONS(i, k, j, v, ~v ) ; 5 ~ := ~ U ~v; 6 end end procedure LOCALPATHCONS(in i, k, j, v, out ~) Pre: i, k, j E node( G). Post: ~1 C ~ C ~2, with ~1; {(v-;w'} E C;j 1-.PCikj(v,w')}. ~2 = {(v',w') E C;j 1-.PCikj(v',w')}. begin 1 BOUNDEDMIN(i , k, j, (v, MAX(v, i,j) ), ~ 1 , Wmin); 2 if Wmin =MAX(v, i,j) then ~ := ~' 3 else 4 begin 5 BoUNDEDMAx( i, k, j, (v, MIN(v, i,j) ), ~ 11 , Wmax); 6 PROPAGATE(i,j,k,(v,wmin}, BOUNDEDMIN, PRED, ~1) ; 7 PROPAGATE(i,j,k,(v,wmin}, BOUNDEDMIN, SUCC, ~2); 8 PROPAGATE(i,j,k,(v,Wmax}, BOUNDEDMAX, PRED, ~3) 9 PROPAGATE(i,j,k,(v,wmax}, BOUNDEDMAX, SUCC, ~4); 10 ~ := ~' u ~" u ~1 u ~2 u ~3 u ~4; 11 end end

An implementation of Procedures PATHCONS and Lo­ CALPATHCONS is given in Figure 4. Note that the spec­ ification of LOCALPATHCONS has been relaxed further by removing parameter u and that PATHCONS can now be expressed in terms of LOCALPATHCONS. In LOCAL­ PATHCONS, BouNDEDMIN computes the interval fl.' to be removed on the left of the interval in row v while BoUNDEDMAX computes the interval fl." to be removed on the right of the interval in row v. Although this prun­ ing is sufficient, it may destroy the CRG property. To preserve the property, it is necessary to perform addi­ tional pruning on the rows above or below v. This is the role of the PROPAGATE instructions. The specifications and implementation of the procedures are given in Fig­ ure 5 and the intuition behind LOCALPATHCONS is cap­ tured in Figure 6. Because C;i := C;i nC;k .Cki produces a CRC constraint, the implementation is guaranteed to keep C;j connected row convex. Note that PROPAGATE works from v to the exterior, while BOUNDEDMIN and BOUNDEDMAX work from the exterior to the interior.

Complexity PRUNE can be performed in 0(/:l.) as­ suming the elements of fl. are ordered to preserve the CRC property. The ordering can be performed during the construction of fl. during LOCALPATHCONS without incurring any cost. An implementation of fl. as a doubly­ linked list is sufficient for this purpose given the way fl. is constructed as mentioned in the previous section. The complexity of Procedures PROPAGATE, BOUNDEDMIN and BOUNDEDMAX is obviously 0(/:l.) . Hence LOCAL­ PATHCONS is 0(/:l.) . By Theorem 7, the time complexity of PC-GEN is O(n 3 d 2 ). The space complexity per con-

procedure PROPAGATE(in i, k, j, (v, w}, BOUNDED, NEXT, out~) Let Vk = NEXTk(v), Wk and ~k such that BOUNDED(i,k,j, (vk,w},~k>wk), m = max{k I ~k # 01\ wk = w}. Post: ~ = U1<k<m+1 ~k begin - - 1 ~ := 0; 2 Veale:= v; 3 repeat 4 Veale :=NEXT(Vcalc); 5 BOUNDED(i, k, j, (vcalc>w}, ~calc> Wcalc); 6 ~ := ~ U ~calc ; 7 until (wcalc # w); end procedure BOUNDEDMIN(in i, k , j, (v,w), out~. Wmin) Post: Wmin = max{w E Dj(Cji) l'v'w' E [MIN(v, i,j),w): EMPTYSUPPORT( v, w', i, k, j)} ~ = { (v,w'} I w 1 E [MIN(v,i,j),wmin]} begin 1 ~ := 0; 2 w2 :=MIN(v,i,j); 3 while (w2 ~ w) 1\ -.EMPTYSUPPORT(v,w2,i,k,j) do 4 begin 5 ~ := ~ U {(v,w2}}; 6 w2 := succ(w2); · 7 end ; 8 Wmin := PRED(w2); end procedure BoUNDEDMAx(in i, k, j, (v, w}, out ~. Wmax) Post: Wmax = min{w E Dj(Cji} l'v'w' E [w,MAX(v,i,j)) : EMPTYSUPPORT(v,w', i, k, j)} ~ = { (v,w') I w' E [wmax,MAX(v,i,j)]} begin 1 ~ := 0; 2 w2 :=MAX(v,i,j); 3 while (w2 2: w) 1\ -.EMPTYSUPPORT(v,w2,i ,kj) do 4 begin 5 ~:=~U{(v,w2}}; 6 W2 := PRED(w2); 7 end ; 8 Wmax := SUCC(w2); end procedure PRUNE( in ~. i, j) Pre: i,j E node(G) , C;j is a CRC constraint, C;j \ ~ is a CRC constraint. Post: C;j = C;j 0 \ {(v,w) I (v,w) E ~}, Cji = Cji 0 \ {(w,v) I (v,w} E ~}.

straint is 0( d) and 0( nd) for all the constraints. The space complexity of the queue is bounded by O(n 2 d) be­ cause procedure LOCALPATH does not use parameter u and elements in the queue can be grouped as tuples of the form (i, j, E, v), where the set E is initially node( G)\ {j} . The set E can be shared by all elements of the queue ex­ cept the first one.

Theorem 8 For CRC constraints, PC-G EN has a time complexity of O(n 3 d 2 ) and a space complexity of 0( n 2 d).

The above theorem is valid for incomplete graphs of CRC constraints as well , since the completion of the graph introduces TRUE constraints which are CRC.

Finding a Solution A path-consistent graph with CRC constraints is decomposable due to Helly's theo­ rem (e.g., [Haroud and Faltings , 1996]) . The proof in [van Beek and Dechter , 1995] is constructive and the author proposes a 0( n 2 d) algorithm to find a solution. We propose in Figure 7 an INSTANTIATE procedure with a time complexity of 0( n 2 ) for CRC constraints. It is based on van Beek's algorithm, but takes advantage of the data struct.ure.

procedure l NSTANTIATE(in G, out (x1, ... , Xn )) Pre: G has only CRC constraints, and is path-consistent, D; :f. 0 (1 ~ i ~ n) Post: (x1, .. . , xn) is a solution of G. begin 1 for i := 1 to n do 2 begin 3 L := FIRST(i ,i) ; 4 for j := 1 to i-1 doL := max( L, MIN(xj,j ,i)) ; 5 Xi: = L 6 end end

The total complexity to detect inconsistency or to find a solution of a graph composed with CRC con­ straints is thus O(n 3 d 2 ) , the time complexity of the path­ consistency algorithm.

7 Conclusion

In this paper , we studied constraint satisfaction over connected row convex (CRC) constraints , a large class of constraints subsuming, in particular, monotone con­ straints. We showed that, contrary to row convex con­ straints, CRC constraints are closed under composition, intersection, and transposition, establishing that path consistency over CRC constraints produces a minimal and decomposable network and strenghtening the results of van Beek and Dechter [1995] . We then presented a path-consistency algorithm for CRC constraints running in time O(n 3 d 2 ) and space O(n 2 d) , where n is the num­ ber of variables and dis the size of the largest domain, as an instantiation of a generic path-consistency algorithm. This improves the traditional time complexity O(n 3 d 3 ) and space complexity O(n 3 d 2 ). Finally, we show that a solution can be found in time O(n 2 ) , once the graph is path-consistent .

Further research will be devoted to studying how to improve path consistency and its approximation to con­ tinuous domains, since path consistency has been shown instrumental in speeding search considerably for some transistor modelling problems , and to other classes of discrete domains.

Acknowledgment We thank anonymous reviewers for helpful comments. This research is partially supported by the Actions de recherche concertees ( ARC/95/00-187} of the Di­ rection generale de la Recherche Scientifique - Communaute Fran~aise de Belgique, by the Office of Naval Research (ONR Grant N00014-94-1-1153 and a NSF National Young Investi­ gator Award with matching funds of Hewlett-Packard.