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