Combination of Nonlinear Terms in Interval Constraint Satisfaction Techniques - Artificial Intelligence and Symbolic Computation - page 124

If the domain of term f is not box consistent then it may be reduced by means
of the narrowing operation θ ( f, C, D ). By Theorem 1 the reduced domain must
be a superset of the range of f R on D .
Box consistency is a method for bounding the range of a term over a domain.
Given a term f andaninterval I ,let f

I denote a projection constraint ,which
means that the range of f R over the current domain must be included in I .We
will assume in this section that there exist ecient algorithms able to compute
such an interval I . An effective implementation will be described in Section 4.
In the following projection constraints will be considered as first-class con-
straints. The purpose of our work is to combine projection constraints in order
to handle the locality problem for the variables occurring in f .

∈

3.1 Term Sharing
The first idea, which may be considered as a well-known result, is to share terms
in NCSPs. It suces to represent the set of constraint expressions as a Directed
Acyclic Graph. As a consequence, intersections of domains do not only happen
at variable nodes but also at non-variable term nodes. The following lemma
shows that projections of different constraints on the same term just need to be
intersected to reduce its domain of possible values.
Lemma 1. Let f be a term and let I and J be two intervals. Then we have:

f ∈ I ∧ f ∈ J = ⇒ f ∈ I ∩ J

This technique is a first approach to handle the locality problem. As shown in
the introduction and in the following example, which corresponds to the use of a
redundant equation. However the redundant equation has not to be represented
since the reductions are directly obtained in the DAG.
Example 3. Consider the conjunction of constraint

cos( xy )=2sin( x ) ∧ cos( xy )+cos( y )=0

10 , 10] 2 . The application of a bisection algorithm at the maximal
machine precision leads to the generation of about 1 . 5

in the box [ −

10 4 · boxes and to the

10 6 interval operations. If the term cos( xy ) is shared then the
number of boxes decreases to 1 . 5

evaluation of 3 ·

10 4 .The
gain is more than one order of magnitude on this problem. In fact sharing the
term cos( xy ) is equivalent to using the redundant constraint 2 sin( x )+cos( y )=0.

10 3 and the number of evaluations is 5

· ·

3.2 Term Combination
The second idea is to mimic elimination procedures for linear and polynomial
systems of equations. The goal is to derive redundant constraints which may
improve the precision of consistency computations and the computation time.
These remarks led us to the following motivations: combination of terms which
can be simplified and reuse of already computed intervals for terms. The notion
of combination function is well-known for linear terms or S-polynomials [5,3].
We give now a general definition to cope with nonlinear combinations.