Consistency Techniques for Numeric CSPs

1 Introduction

Artificial intelligence, operational research and, more recent­ ly, logic programming often use the concept of constraint in order to express and solve a problem. Bit by bit a theoretical framework has evolved, that of Constraint Satisfaction Prp­ blems (CSP) [Waltz, 1972; Montanari, 1974; Mackworth, 1977]. A CSP is defined by a set of variables each with an as­ sociated domain of possible values and a set of constraints on the variables.

This paper deals with CSPs where the constraints are nu­ meric relations and where the domains are either finite integer domains or continuous domains (numeric CSPs). [Davis, 1987] offers a good insight into this kind of problem. Methods exist to solve numeric constraint systems in certain special cases (Simplex algorithm, Grobner bases, Newton's method, etc.) but no general method exists.

Consistency techniques have been successfully applied to general CSPs and could be very useful for numeric constraint systems, but we shall see that even a very simple consistency technique such as arc consistency may tum out to be unrealis­ tic (although the characteristics of numeric CSPs can be used to greatly reduce the complexity of such techniques: (1) nu­ meric constraints are expressed intensionally and (2) the do­ mains are ordered and can also be expressed intensionally).

Interval propagation is another technique, used for solving numeric CSPs. It consists in propagating the bounds of the domains and is often used in implementations either on finite integer domains such as CHIP [Dincbas et al., 1988] and OSL [IBM, 1991] or continuous ones such as BNR-Prolog [Older and Vellino, 1990] and Interlog [Tosello, 1990; Dassault Electronique, 1991]. But interval propagation has never been formalized by a concept of consistency and no complexity analysis has ever been performed.

This paper is a presentation of two new partial consisten­ cies, their specificity being that they only consider the bounds of the domains. The first one formalizes interval propagation, the second, which is stronger than the frrst, has given rise to a new algorithm (implemented in Interlog). An extension of these consistencies enables the running time of algorithms to be tuned.

The paper is organized as follows. Chapter 2 describes the problem. Section 2.1 considers the usefulness of consistency techniques in numeric CSPs. Section 2.2 introduces the abs­ tract concept of numeric value, thanks to which it is possible to provide definitions and algorithms that are valid for both finite and continuous domains. Section 2.3 defines the forma­ lism that has been adopted.

Chapter 3 discusses solving numeric CSPs and first shows that arc consistency may be unrealistic on large size domains. Section 3.1 defines arc B-consistency (where B stands for bounds) which formalizes the interval propagation technique. Section 3.2 introduces 3-B-consistency which is a stronger consistency on domain bounds than arc B-consistency. The algorithms that perform these two consistencies are given and their complexity is analyzed. Section 3.3 contains some expe­ rimental results.

The whole paper has been written with continuous domains in mind (the examples always involve real variables) but it is obvious that everything is equally valid for fmite integer do­ mains. The proof of the propositions and the complexity ana­ lysis can be found in [Lhomme, 1992].

2 Numeric CSPs

2.1 Why consistency techniques are useful

Numeric CSPs can be used to express a large number of pro­ blems, in particular physical models involving inaccurate data or partially defined parameters. Here it is a question of what solving such problems implies. These problems are ge­ nerally under-constrained, i.e. a very large number of solu­ tions exists (infinitely large in the case of continuous do­ mains). Although it is impossible to enumerate all of them, it is often possible to express the set of solutions.

Example: Let three real variables be linked by a constraint U = R · I. If we know that I varies between 1 and 2 and that R varies between 10 and 11, it is not so much one solution that is worth knowing (e.g. R=10.53, I= I, U=l0.53) as the euct nnge of values of U (i.e. the interval [10, 22]).

In this example the domains are continuous and so it is im­ possible to enumerate all the solutions. The constraint U = R *I is non linear, the Simplex cannot apply. The Grob­ ner bases method can be used to solve polynomial equations but cannot take inequations into account

The difficulty comes from the fact that we are trying to reason on the range of values of variables. A natural method would therefore be to attribute a dynamic domain to each va­ riable and to propagate this domain through the constraints. This is exactly what the CSP consistency techniques [Mac­ kworth, 1977] do. We shall use these techniques to try to de­ termine the exact range of values of a set of constrained va­ riables.

Traditionally, domains and consistency techniques in CSPs are only used to simplify a problem before going on to enu­ merate the solutions. In numeric CSPs, however, one of the main ideas is to consider that the domain of a variable is an approximation of the exact range of values of the variable and may itself be of use. This interpretation is similar to Hyvonen's tolerance propagation [Hyvonen, 1989].

Independently of the very large, or even infmitely large number of solutions, another advantage of working on ranges of values rather than on single values is that it allows dynamic numeric CSPs to be handled, i.e. numeric CSPs to which constraints may be added. Incrementality is therefore crucial and requires delaying choice points (which list the solutions to an intermediate numeric CSP) as long as possible. Incre­ mentality is a key feature when integrating consistency tech­ niques in a programming language (see [Cleary, 1987; Dine­ bas et al., 1988; Older and Vellino, 1990; Sidebottom and Ha­ vens, 1991; Lee and Van Emden, 1992; Benhamou and Older, 1992]).

2.2 The concept of numeric values

In order to be able to use the same language both for fmite and for continuous domains, the abstract concept of numeric va­ lue has been adopted. It will be defined separately for finite domains and continuous ones.

When a domain is fmite, a numeric value is simply defined by:

Definition la: numeric values in fmite domains

For a finite nwneric domain D a numeric value is an element of D.

In the case of continuous domains, the domain associated with a variable represents an infinite set of real numbers. However, since a computer handles real numbers through floating-point numbers it is important to have a formalism that allows for this, without which no valid result could ever be obtained. In floating-point representation the set of values that a numeric variable can take is the set of floating-point numbers {{0, ... /nl. A real number between two consecutive floating-point numbers is usually approximated. In order to avoid approximations and guarantee correct results, a nume­ ric value in a continuous domain is defined as follows:

Definition lb: numeric values in continuous domains A numeric value is an element of the set { (-00/o) ./o, lfofJ), f1 · lfJh) ,f2 · ··· ./~, lfn,+oo) }.

A numeric value is either a floating-point number for an open interval whose bounds are two consecutive floating point numbers 1 (J,f+) or one of the terms (-oo/0) or lfn,+oo) representing the infinities. The interval (f,f+) represents an infinite set of real numbers but will be considered as a single value. This defmition enables us to consider the domain asso­ ciated with a variable as a finite set while preserving the con­ tinuity of the domain. Note that an open interval will also be represented by a fmite set (and will therefore be closed).

Exampl~: The half-open interval [2,3) shall be considered as the fmite set { 2, (2,2+), 2+ , ... , 3-, (3-,3) } and shall be represented in our no­ tation by a closed interval [a,b) with a=2 and b=(3-,3).

Interval arithmetic [Moore, 1966; Alefeld and Herzberger, 1983] provides computing methods that respect this forma­ lism (and in particular allow the symbolic handling of infini­ ties). Whereas computations performed using a floating-point representation are a mere estimate of the correct result, inter­ val-based computing methods provide an interval and gua­ rantee2 bounds for this correct result. The advantage of inter­ val arithmetic is not just a matter of checking computing er­ rors; it also offers ways to reason on the range of values of variables.

2.3 Definitions

By NCSP we mean a Numeric Constraint Satisfaction Pro­ blem. The corresponding definitions are almost the same as for CSPs [Mackworth, 1977] except that the constraints can­ not be given extensionally.

Definition 2: an NCSP

An NCSP P = (V,D,C) is defined by

• a set of numeric variables V = {X 1 , ... X,J
• -a set of domains D = {D1, ... D,J where Di, a set of numeric values, is the domain associated with the variable Xi
• -a set of constraints C ={C1, .. . C,J where a constraint Ci is defined by any nwneric relation linking a set of variables.

Exampl~: Figure 1 defmes three NCSPs that will be used later (P 1 , P 2 and P3 differ only by their domains).

Definition 3: solution to an NCSP

A solution to an NCSP P = (V .D ,C) is an instantiation of the variables of V for which both inclusion in the associated do­ mains and all the constraints of C are satisfied.

Example: {X=l,Y=l} and {X=(l-,1), Y=(l,l+)} are two solutions 1 to Pl .

Definition 4: global consistency of an NCSP

Let P = (V,D,C) an NCSP, Pis globally consistent iff V X E V, V a E Dx. X = a belongs to a solution toP.

Global consistency reflects the fact that for any variable X of the problem, the domain Ox is the projection of the set of solutions toP on X. Unlike Freuder's global consistency for CSPs [Freuder, 1988], this definition allows constraints that are given intensionally.

Example: It is easy to verify that P3 is globally consistent.

Definition 5: equivalence of two NCSPs

P and P' are equivalent (P = P') iff they have the same set of solutions.

Example: P1 "' P2 "' P3.

We will use the following terminology when talking about consistency techniques (see [Jegou, 1991]). A partial consis­ tency A (e.g. A= arc or path consistency) is a property of a CSP. Let P be a CSP. Closure by A of P, denoted <J)A.(P), is informally the largest CSP included in P for which A consis­ tency holds. A A filtering algorithm computes <J)A.(P) and is usually called a consistency technique.

Let us now look at a number of concepts that will be used later on.

If Ox is the domain of a variable X, we say that Ox is con­ vex iff all the numeric values between min( Ox) and max(Dx:) belong to Dx· If D1 , .. . , Dk are convex then E = D1 x ... x Dk shall be called a box.

Definition 6: projection of a constraint

Let XJ. .. ·· Xk be k variables, let E = D 1 x ... x Dk. The projec­ tion over X; of the constraint C(XJ. .... Xt) restricted to domains D Jo ... ,Dk that shall be denotedfi;(C(X1 .... Xt). E) is the set: { v; E D;l 3 (v1, .. . , v;.1· v;+1, ... ,vt) ED 1 x .. . x D;.1 x D;+1 x ... x Dk such that C(vJo .. ,vt) is satisfied}.

Example: Given a constraint Y = X 2 . Let Dx = [-2,+2], Dy = [1,10], E=Dx:XDy, so nx ( {Y = X 2 }, E)= [-2,-1] u [1,2] and ny ( {Y = X 2 }, E)= [1,4].

For reasons of efficiency of implementations the concept of basic constraint now needs to be introduced.

Definition 7: basic constraint

A constraint C(XJ. .. ·· Xt) is said to be !Jasic iffV i E 1 .. k, it is possible to show two functions frm and F;max such that, for any box E = D1 x ... x Dk, Frm(E) and F;max(E) are the min and max values ofll;( C(X1, .... Xt), E).

Please note that the rest of this paper assumes that the cons­ traints are basic.

Remark 1: a small set of basic constraints enables a large number of basic constraints to be expressed (through the con­ junction3 of constraints and addition of intermediate variables). In Interlog, over continuous domains, given X, Y and Z distinct variables, the following set { X = Y, X~ Y, Z =X+ Y, Z = X*Y, Y =-X, Y =sin X, Y =cos X, Y =ex, Y = abs(X), Z = xY, z = min(X,Y), Z = max(X,Y) ) is a set of basic constraints, thanks to interval arithmetic. The constraint Z = X* X+ Y is basic but it is not in the set; it may be expressed by (Z = VI+Y) & (VI= X2).

I. Remember that operations are perlormed by interval arithmetic methods: so (1-,1) + (1,1+) = [a,b] and [a,b] is such that [a,b] contains 2.

2 · if and only if.

3· The conjunction of basic constraints is not always a basic constraint.

Remark 2: when a constraint is not basic it is often possible to transform 4 it into a conjunction of basic constraints (e.g. eX = sin (X+Y) becomes (ex = VI) & (VI = sin V2) & (V2=X+Y)).

A constraint is said disjunctive if it "destroys" the convexi­ ty of its domains. This concept depends on the domain of va­ riables: the same constraint can be disjunctive for certain do­ mains but non disjunctive for others.

Definition 8: disjunctive constraints

A constraint C(XJ. .... Xt) is disjunctive for the box E = D 1 X ... X D k iff

3 i E 1 .. k, fl;( C(X1, ... , Xt), E) is non convex.

Examples: The constraint X 2 = Y is non disjunctive for Dx=l -2, 2] and Dy = [0, 4], is disjunctive for Dx=[-2,2] and Dy = [1, 4], is non dis­ junctive for Dx=[l, 2] and Dy = [1,4].

3 How to solve an NCSP

The goal here is neither to enumerate all the solutions nor to algebraically solve a system of constraints but to determine the exact ranges of values of the different variables. If it were possible to find an NCSP that was equivalent and globally consistent the goal would be reached. But the search for glo­ bal consistency is an NP-hard problem 5 .

A natural approach, that has proved its worth on CSPs, is to begin by trying to reach partial consistency. Arc consistency 6 could seem a good beginning. Unfortunately, if there are any disjunctive constraints in the system arc consistency can rapi­ dly lead to combinatorial explosion. If we look at the example below we shall soon see that this approach is unsuitable.

Example: Dx= [0, 31416], Dy= [0, 31416], Dz= (-oo, +oo), sin X= 0.2, cosY= 0.1, Z =X* Y.

Arc consistency would lead to the union of 1 cf intervals for Dx and Dy (lrf =the number of monotonic parts of sine and cosine in [0,31426]) and to lOS intervals for Dz. Such a combinatorial explosion is totally unreasonable.

The above example is an extreme case but there are only three constraints! Even without this kind of extreme case, as soon as the number of constraints becomes rather large there is a risk of combinatorial explosion due to the representation of the domains.

In NCSPs the domains that are handled are finite but of a very particular kind: they are by definition very large 7 and are ordered. A very economical way of representing a convex do­ main is to do so intensionally by just one interval (i.e. two bounds). Accordingly, if we only handle convex domains, the combinatorial explosion due to the representation of domains can be avoided. This brings us on to the definition of new par­ tial consistencies. Whereas partial consistencies arising from CSPs guarantee conditions over all the elements of a domain, the new consistencies will guarantee conditions only over the bounds of the domain and will thus preserve convexity.

4 · Under such transformations, global consistency is invariant but partial con­ sistencies are generally not invariant.

s. It is an uncomputable problem over the real numbers (because of the trans­ cendental functions) but in fmite precision it becomes an NP-hard problem.

6 · Let P be an NCSP, X a variable of P. Dx is arc consistent iff '1:1 C(X, X1, .. . ,X.J a constraint over X, '1:1 v e Dx.

3 v1, ... , Vk E 0 1 X ... X~ I C(v, v1, ... , v.J is satisfied. An NCSP is arc consistent iff all the domains are arc consistent.

7 · The number of 64-bit floating-point numbers between 0.0 and 1000.0 is of the order of 4.6 * 10 18 on an IBM 3090.

Moreover the constraints are also given intensionally. In­ terval arithmetic will thus make it possible to give very effi­ cient filtering algorithms.

Subsequently only convex domains will be handled and the domain associated with a variable will simply be an interval. In addition, thanks to our representation of open intervals (see section 2.2), only closed intervals have to be handled.

3.1 Arc B-consistency and interval propagation

Arc B-consistency (B for bounds) is a partial consistency de­ fined as follows:

Definition 9: arc B-consistency

Let P be an NCSP, X a variable of P, Dx = [a,b]. Dx is arc B-consistent iff'r:l C(X, X1, ... .XJJ a constraint over X 3 v1, .. . , vk E D 1 x ... x Dkl C(a, v1 · ... , vtJ is satisfied, 3 VJ> ..· , vk E D1 x ... xDkl C(b, VJ> ·.. , vJJ is satisfied. An NCSP is arc B-consistent iff all the domains are arc B-consistent.

Informally arc B-consistency is a form of arc consistency that is restricted to the bounds of the domain.

E=mple: It is easy to verify that P 2 (see Figure 1) is arc B-consistent.

The difference between arc B-consistency and arc consis­ tency comes from the way the disjunctive constraints are han­ dled. Arc B-consistency encompasses in one single interval the domain of a variable; some values of a domain may be lo­ cally inconsistent.

E=mple 1: Let P be defmed by Dx: = [1,4], Dy = [-2,+2], X=Y 2 ,

P is arc B-consistent but not arc consistent (the value 0 of Dy does not correspond to any value of Dx: such that the constraint can be satisfied).

Closure by arc B-consistency is defmed as follows:

Definition 10: closure by arc B-consistency

Given an NCSP P where P = (V,D,C). Closure by arc B-con­ sistency ofP, denotedci>As(P), is anNCSP P' where P' = (V,

D',C) and P' such that: P'=P, P' is arc B-consistent, 'r:l D;' E D',D;' ~D;. there is no P"=(V, D", C) such that P" is arc B.-consistent, P" = P, P":F. P', 'r:l D;' E D', D;' r;;;;,D;".

Example: We have Pz = cliAB(Pl).

It can be proved that ci> As(P) always exists and is unique. ci> As(P) may be the empty NCSP (i.e. the domains are equal to 0), in which case P has no solution.

By denoting closure by arc consistency of Pas ci> Ac(P), the relations between arc B-consistency and arc consistency can be expressed by the. following theorem.

Theorem 1

Given an NCSP P where P = (V ,D,C) and D = {D 1· ··· , D,J. Let P' = cl>As(P) and P" = cl>Ac(P), then 'rl i E 1 .. n, D;' is the smallest interval encompassing D /' .

Corollary 1

Let P be an NCSP that contains no disjunctive constraints over the domains being considered. So Pis arc B-consistent iff P is arc consistent.

Example: The NCSP P2 is arc B-consistent, all the constraints of Pz are non disjunctive, therefore P 2 is arc consistent. However, the NCSP of example l above (with the constraint X = Y 2 ) is not arc consistent.

Figure 2 shows an algorithm (called IP _1 for interval propagation) to compute closure by arc B-consistency. This al­ gorithm looks very much like that of Waltz [1972] and also like AC-3 [Mackworth, 1977]. The difference lies in the way disjunctive constraints are processed, which is by bounding the result within a single interval (i.e. a constraint will not de­ lete an impossible value between possible values).

procedure IP _l(lnout P) Precondition:P 0 isanNCSP. Pas/condition: either P is the closure by arc B-consistency of P 0 or exit with failure. Begin 1 Agenda := { <C, X> I C is a constraint of P, X is a variable of C} 2 while Agenda "#- 0 3 select and delete <C, X> from Agenda 4 REVISE( <C, X>, Result) 5 If Result = fail then exit with failure 6 If Result =changed then 7 Agenda:= Agenda v { <C', X'> I C"T-C, X inC' and X'"T-X } 8 end while end IP _l procedure REVISE( <C.X>, Result) Begin 9 let pnin and P""" be the functions of defmition 7 for C and X lOrn := pnin over D1 ... Dn; M := P""" over 0 1 ··· Dn 11 if m and M do not exist then Result := fail 12elsif Dx 'I' [m.MJ then % [m,M) is always included in Dx 13 Dx: := [m,M) 14 Result := changed 15 else Result :=nothing end REVISE Figure 2: IP _1

Description of IP _1. Lines 3 and 4 remove a pair <C, X> from the agenda and call the REVISE procedure which tries to restrict Dx- If Dx has been modified (line 6), the pairs <C', X'> that are likely to narrow a domain are added to the agen­ da (line 7).

The REVISE procedure uses the particularities of basic cons­ traints: it is possible to compute the min and max of the pro­ jection of the constraint over the variable X (lines 9 and 10).

Terminating the IP _1 algorithm. Over continuous do­ mains, IP _1 can lead to problems of termination.

Example: Let P be defmed by: (a) Y = X+l, (b) y = 2. x. Dx: = [0,10], Dy = (-oo,+oo). Dx: = [0,10) leads, according to (a), to Dy = [1,111 Dy = [1,11) leads, according to (b), to Dx = [0.5, 5.5] Dx: = [0.5, 5.5) leads, according to (a), to Dy = [1.5, 6.5) Dy = [1.5, 6.5] leads, according to (b), to Dx: = [0.75, 3.25]

A phenomenon of iteration and asymptotic convergence towards the solution (X= 1, Y =2) occurs. In twenty iterations the degree of precision obtained is Jess than 10- 6 and gives the result Dx = [0.999999 , 1.000001 J. Dy = [ 1.999999 , 2.000001].

Termination of this algorithm over continuous domains could naively give rise to two types of discourse.

• The first one says that since the number of floating point numbers is finite, termination can easily be shown (a domain can only be restricted). But this attitude is of very little practical interest and the algorithm can take a long time terminating.
• The second one is directly linked to the implementation. It involves interrupting propagation before normal ter­ mination (e.g. by giving a time limit or, when a domain is restricted to less than E - absolute or relative - by not reactivating the constraints concerned). The problem this time is that, when the algorithm terminates, it is not possible to describe the status of the domains (the NCSP is neither arc B-consistent nor anything like it).

What could be done is a third way that avoids the draw­ backs of the first two. This requires defining arc B(w)-consis­ tency, which generalizes arc B-consistency, and then modi­ fying IP _1 so as to compute filtering by arc B(w)-consisten­ cy. Thew (as width) characterizes authorized imprecision at the bounds.

Notation: ifv is a numeric value and k a positive integer, v+k (resp. v·k) is the kth greater (resp. smaller) value than v if it exists. /fit does not exist , v+k (resp. v·k) will be the maximum (resp. minimum) numeric value. Note that ifk equals 0, v+ 0 =

v·O = V.

Definition 11: arc B(w)-consistency Let P be an NCSP, X a variable of P, Dx = [a,b], w a positive integer. Dx is arc B(w )-consistent iff V C(X, X1- ... XJJ a constraint over X 3 v E [a, a+w] , 3 v 1 , ...· vk ED 1 x ... xDk f C(v, v1, ... · vJJ is satisfied, 3 v E [b-w. b), 3 VJ , .. . , vk E D1 x ... x Dk I C(v, VJ. ... , vJJ is satisfied. An NCSP is arc B(w)-consistent iff all its domains are arc B(w )-consistent.

Arc B(O)-consistency is equivalent to arc B-consistency.

Proposition 1

Let P be an arc B(w)-consistent NCSP,let w';;:: w, hence Pis arc B(w' )-consistent.

It is possible to define a closure by arc B(w)-consistency. Unlike closure by arc B-consistency, this one is not unique and depends on the order in which the constraints are evalua­ ted. The IP _2 algorithm shown in Figure 3 computes one of these closures, denoted <l>AB(w)(P).

Description ofiP _ 2. The IP _2 procedure differs from IP _1 in the parameter w and the function SUFFICIENT CHAN­ GE. The function SUFFICIENT CHANGE is true if at least one of the bounds of Dx is more than w distant from the cor­ responding bound of [m,M]. When it can be seen that a cons­ traint will move the two bounds of a domain by less than or equal tow, then (line 15) it is not applied (in fact it is satisfied in terms of arc B(w)-consistency). If this constraint were to be applied systematically 1 (if the assignment of line 13 were to be performed before the test of line 12), it would be impossi­ ble to define a strict semantics. Obviously, if w = 0, IP _2 is equivalent to IP _I.

I. This is the case for BNR-Prolog, for example.

Complexity. Let A be the maximum domain size, let a= A/(w + 1) (a characterizes the number of packets of (w+1) va­ lues in a domain) and let m be the total number of constraints of P. The complexity analysis (see [Lhomme, 1992]) shows that the worst case running time of IP _2 is bounded below by Q(m) and above by O(am). The lower bound of the worst case running time of IP _2 is independent of A. This is all the more useful as the domains being handled are large.

The complexity of IP _1 follows immediately from this (by taking w=O, and therefore A=a). It is bounded by Q(m) and O(Am). For non disjunctive constraints, arc B-consistency is equivalent to arc consistency and IP _1 can be compared with arc consistency algorithms. Mackworth and Freuder [1985] have given the lower and upper bounds of the worst case run­ ning time of AC-3: Q(A 2 m) and O(A 3 m). AC-4 [Mohr and Henderson, 1986] does not apply here because the domain size is too large (AC-4 associates a data structure with each value of the domain). Deville and Van Hentenryck [1991] and Perlin [ 1992] suggest taking the constraint semantics into account. For certain classes of constraints, the worst case run­ ning time of their algorithms is also O(Am).

3.2 Stronger consistency: 3-B-consistency

Neither arc B-consistency nor arc consistency are always suf­ ficient:

Example: P2 is arc B-consistent (and even arc consistent) but it does not allow the range of values of the variables to be found i.e. Dx=[0.5, 1), Dy=[l , 1.5].

In the case of CSPs over finite domains, an efficient way of finding solutions is often to perform an interleaved enumera­ tion with arc consistency filtering. One of the ways of adap­ ting this method to NCSPs is domain splitting [Cleary, 1987]: if Pis arc B-consistent, the domain of a variable is split in two and the two resulting NCSPs are explored separately. This process introduces choice points and can rapidly lead to com­ binatorial explosion.

A different approach would be the definition of a stronger consistency than arc B-consistency (and that shall be called 3-B-consistency) and the description of a flltering algorithm that computes closure by 3-B-consistency. In order to avoid combinatorial explosion, 3-B-consistency guarantees condi­ tions only on the bounds of the domains. Intuitively, 3-B-con­ sistency can be seen as a form of strong 3-consistency [Freu­ der, 1988] restricted to the bounds of the domains.

Notation: The union of an NCSP P = (V ,D,C) and a cons­ traint K (which only constrains variables that are already present in P) is defined by: P' = P u {K} = (V .D.C u {K})

Definition 12: 3-B-consistency

Let P be anNCSP, let X be a variable ofP, and Dx = [a,b]. Dx is 3-B-consistent iff P' and P" are both non empty whereP' = cl>AB(Pu {X =a})andP" = cl>AB(Pu {X= b)). An NCSP is 3-B-consistent iff all its domains are 3-B-consis­ tent. Notation: ci>3_Bc(P) represents the closure of P by 3-B-con­ sistency. Example: P 1 and P 2 an: not 3-B-consistent but P3 is 3-B-consistent. In addition P3 = ~3-BC(P1) = ~.ac(Pz).

Before giving a 3-B-consistency filtering algorithm the concept of 3-B-consistency is generalized by 3-B(wJ ,w2)-­ consistency so as to give the bounds a width (authorized im­ precision).

Definition 13: 3-B(w1,w2)-consistency Let P be an NCSP, X a variable of P, Dx = [a,b], and wl ;:>: w2;:>:0. Dx is 3-B(wl,w2)-consistent iffP' andP" are both non empty where P' = cl>AB(w2/ P u {X e ta 1 a+wl])) and P" = cl>AB(w2/ P u {X e [b.w , b])). An NCSP is 3-B(wl ,w2)-consistent iff all its domains are 3-B(wl ,w2)-consistent.

3-B-consistency is equivalent to 3-B(O,O)-consistency. The following proposition corresponds to proposition 1 for 3-B-consistency.

Proposition 2

Let P be a 3-B(wl ,w2)-consistent NCSP, wl' ;:>: wl, w2' ;:>: w2, hence Pis 3-B(wl' ,w2' )-consistent.

A 3-B-consistency filtering algorithm is shown in Figure 4. It has been implemented in Interlog. The principle underlying this algorithm is based on proof by refutation, hence its name, Ref.filtering. Let us assume P to be an arc B-consistent NCSP, X a variable of P, and Dx = [a,b]. We are going to try to restrict Dx by increasing its lower bound. Let it be a point c e (a,b). Now add the constraint X e [a,c). If interval pro­ pagation detects a contradiction we can affirm that the range of values of X is included in [c,b]. If, on the other hand, no contradiction is detected, we cannot be sure of anything, but we can repeat the process with a point c' that is closer to a than c (for instance we could take c' midway between [a,c]).

Description. The index i specifies a pair (X, bound) where X is a variable and bound is either LOW or UP. The index i therefore varies between 1 and 2n. The procedure IP _3 is an incremental version ofiP _2: the first parameter is an NCSP P which is arc B(w2)-consistent, and the second parameter is a constraint to add toP. The function assign(i,size) returns a constraint that corresponds to the instantiation of X at its bound enlarged to size elements. The function delete ele­ ments(i, size) returns the complementary constraint ofassi­ gn(i,size). For instance, if Dx = [a,b], and if bqund equals LOW, assign returns the constraint "X e [a, a;s,zel" and de­ lete _elements returns the constraint "X e [a+(sue+ 1 }, b]".

Complexity. Remember that m is the number of cons­ traints, n is the number of variables, and A is the domain size. Note a1 =AI (w1+ 1) and a2 =A /(w2+ 1). The complexity ana­ lysis (see [Lhomme, 1992]) shows that the worst case running time of Ref .filtering is bounded below by O(n log2 al) and above by O(mn 2 a 1a2). Over finite integer domains, if we take wl = w2 = 0 (i.e. ai = a2 = A), these values become O(n log2 A) and O(mn :A 2 ).

procedure Ref_flltering(lnout P, In w1,1n w2) PrecoNlition: P 0 is an NCSP which is arc B(w2)-consistent. PostcoNlition: either Pis a closure by 3-B(wl,w2)-consiste11Cy of P 0 or exit with failure begin 1 size := A /* A is an upper bound for the size of domains ·t 2 repeat 3 size := size dlv 2 4 repeat 5 fixed _point := true 6 i := 1 7 while i <= 2 · n 8 P' :=P 9 Result := IP _3(P', assign(i,size), w2) 10 lr Result= failun: then 11 Result_2:=IP _3( P, delete_elements(i,size), w2) 12 If Result_2 = failun: then exit with failun: 13 ftxed_point:= false 14 else 15 i := i+l 16 end {while} 17 until ftxed_point IS until size<= w1 end Ref_filtering Figure 4: Ref _r.Jtering

It should be observed that this algorithm can be improved: corollary 2 defines for an NCSP P = (V ,D,C) a partition of V corresponding to equivalence classes. A closure by 3-B(wJ ,w2)-consistency of P could thus be computed by con­ sidering just one representative of each class.

Theorem 2

Let P be an arc B(w2)-consistent NCSP, let X andY be two variables of P linked by a binary, one-to-one monotonic rela­ tion over Dx and Dy. If Dx is 3-B(wl,w2)-consistent then Dy is 3-B(wl' ,w2)-consistent with wl' =constant* wl.

The constant linking wl and wl' is a bound of the derivati­ ve of the relation over the domains Dx and Dy.

Corollary 2

Let P be an arc B-consistent NCSP, let X andY be two varia­ bles ofP such that there exists a sequence X0X1 · .. . , Xk (with Xo=X, Xk=Y) and Xi and Xi+llinked by a binary, one-to-one monotonic relation over Di and Di+l· If X is 3-B(wl ,w2)-con­ sistent then Y is 3-B(wl' ,w2)-consistent with wl' = constant* wl.

Example: Let P be defmed by X= 4·Z + 3, Z = 3·log(Y-l), T = Y"2. Dx = Dv = 0z =Dr= [2,1000}.

The four variables of Pare in the same equivalence class. All that needs to be done is to compute 3-B(wl,w2)-consistency on one of these va­ riables in order to obuin 3-B(wl' ,w2)-consistency of P.

3.3 Experimental results

Arc B-consistency filtering (i.e. interval propagation) is a technique that has already been used and validated experi­ mentally on both fmite domains (CHIP, OSL) and continuous domains (BNR-Prolog, Interlog). 3-B-consistency flltering, however, is new and deserves in-depth experimentation. Here, suffice it to say that in the case ofP1 and P2 ,Ref _.filte­ ring would allow the range of values of each variable to be found rapidly (thus giving P3), whereas the domain splitting technique (see section 3.2) would give a very huge number of contiguous solutions. In addition, even in more complicated cases such as that given in the example below, computation times have in practice turned out to be considerably lower than those predicted from the complexity analysis.

Example: Let P be the NCSP: D,c=[O,l 000], Dy=[O,l 000], Dz=[0,3.1416], Dr=£0,3.1416], X*Y + T- 2*Z = 4 X* sin Z + Y*cos T = 0 X-Y+cos 2 Z=sin 2 T X*Y*Z=2*T with the solution X = Y = 2, Z = 'lt/2, T = 1t. P is arc B-consistent and therefore interval propagation cannot narrow any of the domains. Re!L_Iltering, with wl and w2 corresponding to a relative precision 1 of 10 gives the following result after roughly 10" elementary operations: Dx = [1.9999. 2.0001], Dy = [1.9999, 2.0001], Dz = [1.5636. 1.5701],

0,. = [3.1273 · 3.1416].

This system of constraints decomposes into a system of 22 basic cons­ traints and 22 variables. On an ffiM 3090 the number of numeric values in [0, 1000] is roughly 10 19 , and a relative precision of lo-4 corresponds to wl = w2 = 10 12 · Complexity analysis predicts a number of elementa­ ry operations between 500 and 10 18 · Experimental results are relatively close to the lower bound.

The drawback of domain splitting in the above example is less serious than for P1 and P2 because the solution here is a single value. But it gives many quadruplets <Ox. Dy, Dz, ~) that are close to the solution and is incapable of determining which one actually contains the solution.

4 Conclusion

CSP consistency techniques can be used in NCSPs to deter­ mine the range of values of variables. However their com­ plexity remains too high, even though it can be greatly redu­ ced by the structure specific to NCSPs_

The advantage of the two new partial consistencies, arc B-consistency and 3-B-consistency, is that they are well adapted to NCSPs. Their distinguishing feature is that they only consider the bounds of the domains. As for non disjunc­ tive constraints, it has been shown that arc B-consistency is equivalent to arc consistency. An extension of these B-con­ sistencies introduces the concept of bound width and enables the complexity of algorithms (even on continuous domains) to be tuned. In [Lhomme, 1993] these partial consistencies are generalized by defining k-B-consistency.

I. On continuous domains, k. (in v+~ characterizes a relative imprecision on v (for v ~ 0), whereas on fmite domains k. characterizes an absoluJe impreci­ sion.

Acknowledgments

Palrick Tailllben introduced me to the problems d"~t'riboiJ here and gave invaluable help in preparing this paper. My thanks also go to Michel Rueher, m,· Phn supervisor, for his useful suggestions and constructive criticism. I would also like to thank Bernard Botella, Philippe Jegou, Jimmy Lee, Philippe Marguerie and Franck Porcher for their useful com­ ments on previous drafts of this paper. Finally, my thanks go to Rosalind Greenstein for the English version of this paper.