Information Technology Reference
In-Depth Information
box D ,avariable x i and two constraints C and C the following inclusion holds,
though the equality is not verified in general:
C ,D )
Π x i ( C ,D )
Π x i ( C
Π x i ( C, D )
(1)
Example 2. Consider the NCSP defined by two constraints C : x 1 + x 2 =0and
C : x 1
1 , 1] 2 . The projections over x 1 are as follows:
x 2 =0andthebox D =[
C ,D )=[0 , 0]
1 , 1] = Π x 1 ( C, D )= Π x 1 ( C ,D )
Π x 1 ( C
[
The problem of processing existential quantifications in the definition of pro-
jections is intractable. A main idea is then to implement constraint satisfaction
in the interval domain, which leads to the narrowing procedure called box con-
sistency [2]. In the following, the restriction of the original definition to natural
forms is given:
Definition 1 (Box consistency). Consider a constraint C ( x 1 ,...,x n ) ,abox
D
n and a natural i that belongs to the set
I
{
1 ,...,n
}
. The domain D i is said
to be box consistent wrt. C if we have:
D i =
{
a
D i
|
( D 1 ,...,D i− 1 ,
{
a
}
,D i +1 ,...,D n )
C I }
The corresponding narrowing procedure allows one to reduce the domain D i if
the equality is not verified, using the following operation:
θ :( x i ,C,D )
{
a
D i
|
( D 1 ,...,D i− 1 ,
{
a
}
,D i +1 ,...,D n )
C I }
This operation computes an approximation of the projection of C on x i in D .
The narrowing procedure is complete, since the computed domain encloses the
corresponding projection, that is:
Π x i ( C, D )
θ ( x i ,C,D )
(2)
However the resulting interval may be arbitrarily large wrt. the projection. This
is closely related to the dependency problem of interval arithmetic, which leads
to weak interval computations [8].
3
Symbolic-Numeric Techniques
Box consistency and projections have been defined wrt. the variables. Noticing
that variables are instances of terms leads to generalize these notions.
Definition 2 (Box consistency on terms). Let C ( x 1 ,...,x n ) be a constraint.
Consider a box D
n and a term f occurring in C .Let x n +1 be a fresh variable
and let the constraint C be C [ f
I
x n +1 ] . The domain f I ( D ) is said to be box
consistent wrt. C if we have:
C I }
f I ( D )=
{
a
f I ( D )
|
( D 1 ,...,D n ,
{
a
}
)
Search WWH ::

Custom Search