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

the interval I defined by the set . The standard defines two

rounding operations that associate to each real number a the closest floating-
point numbers

{ a ∈ R | I a I }

. These operations enable
the computation of the convex hull of every set of real numbers A , defined
by the interval:

a and a such that a a a

A =[ inf A , sup A ] . Then µ maps every real number a

to the interval I

are naturally extended to interval vectors. It is worth noticing that an interval
vector D =( D 1 ,...,D n ) is a machine representation of the box D 1 ×···×

{ a } . The membership, union and intersection operations in

D n .
In the following, interval vectors and associated Cartesian products will simply
be called boxes .

Terms. Interval arithmetic is a reliable extension of real arithmetic in the sense
that every interval computation results in a superset of the result of the corre-
sponding real computation. Arithmetic operations and elementary functions are
implemented by computation over interval bounds according to monotonicity
properties. For instance, given two intervals I =[ a, b ]and J =[ c, d ], µ maps
the addition and subtraction operations and the exponential function to the
following interval functions:

I + J =[ a + c , b + d ]

I − J =[ a − d , b − c ]

exp( I )=[ exp( a ) , exp( b ) ]

It is worth noticing that term evaluation in Σ I exactly corresponds to the appli-
cation of an interval function called natural form . The main result from interval
arithmetic is the following inclusion theorem:

n the following

Theorem 1. Consider a term f ( x 1 ,...,x n ) . Then for all D ∈ I

property holds:

{ f R ( a 1 ,...,a n ) | a 1 ∈ D 1 ,...,a n ∈ D n }⊆ f I ( D 1 ,...,D n ) .

Informally speaking, the evaluation of f I is a superset of the range of f R on the
domain D .

Constraints. The interval versions of relations originate from an existential ex-
tension of real relations. For instance, given two intervals I =[ a, b ]and J =[ c, d ],
µ maps equations and inequalities to the following predicates:
I = J

⇐⇒ ∃ u ∈ I ∃ v ∈ J : u = v ⇐⇒ max( a, c ) min( b, d )

I J ⇐⇒ ∃ u ∈ I ∃ v ∈ J : u v ⇐⇒ a d

Constraint satisfaction in Σ I uses natural forms of terms and existential exten-
sions of relations. The aim is to compute reliable approximations of constraint
solutions, which leads to the following theorem:

n we have:

Theorem 2. Consider a constraint C ( x 1 ,...,x n ) . Then for all D ∈ I

∃ a 1 ∈ D 1 ... ∃ a n ∈ D n :( a 1 ,...,a n ) ∈ C R ⇒

( D 1 ,...,D n )

∈ C I .

=