Information Technology Reference
In-Depth Information
The following lemma provides a sucient condition for defining ecient simplifi-
cation functions. The aim is to derive more precise interval functions. Given two
terms
f
and
g
,
g
is said to be
more precise
than
f
if for all
D
n
,
g
I
(
D
)
∈
I
⊆
f
I
(
D
)
holds. This relation defines a partial ordering
on terms (here we have
g
f
).
Lemma 5.
Let
f
(
x
1
,...,x
n
)
be a term and let
g
be a term resulting from a
simplification of
f
.Let
x
i
be a variable occurring in
f
and
g
. Suppose that
g
is
more precise than
f
. Then for every interval
I
and every box
D
the following
result holds:
θ
(
x
i
,g
∈
I,D
)
⊆
θ
(
x
i
,f
∈
I,D
)
The dependency problem of interval arithmetic underlines the weakness of
interval evaluation wrt. multiple occurrences of variables [14]. More precisely,
two occurrences of one variable are processed as two different variables. As a
consequence, there is no elimination of values as in the domain of real numbers. In
this paper, we define the simplification procedure as an application in sequence of
elementary rules supposed to handle the dependency problem. A non exhaustive
set of rules is given below
1
,where
f
,
g
and
h
are terms:
e
f
/e
g
e
f−g
exp :
→
lin :
fg
+
fh
→
f
(
g
+
h
)
div :
fg/fh
→
g/h
It can be shown that each rule
f
f
. In particular the second
one looks like the sub-distributivity property of interval arithmetic. Moreover,
every sequence of application of rules is finite. It su
ces to remark that the
number of symbols in rewritten terms strictly decreases.
→
g
is such that
g
Example 4.
Consider the NCSP
x
2
exp(
−
2
.
5
x
1
)=0
.
85
∧
x
2
exp(
−
1
.
5
x
1
)=1
.
25
given the box [0
,
1]
[0
,
10]. Constraint propagation leads to slow convergence.
This behavior is illustrated in Figure 1 where
x
2
is expressed as a function of
x
1
.
The initial box is first reduced at the upper bound of
x
2
using
g
2
: the eliminated
box contains no solution of the second constraint,
i.e.
, no point of
g
2
. Then the
upper bound of
x
1
is contracted using
g
1
,andsoon.
The two constraints can be combined and simplified as follows:
×
x
2
exp(
−
2
.
5
x
1
)
1
.
5
x
1
)
=
0
.
85
exp(
−
2
.
5
x
1
)
=
0
.
85
1
.
25
div
−→
exp
−→
x
2
exp(
−
1
.
25
exp(
−
1
.
5
x
1
)
x
1
)=
0
.
85
1
.
25
If the redundant constraint is added in the NCSP, a gain of more than one order
of magnitude is obtained in the solving process using box consistency. The result
is the box [0
.
38566248
,
0
.
38566249]
2
.
5
x
1
+1
.
5
x
1
)=
0
.
85
1
.
25
lin
−→
exp(
−
exp(
−
×
[2
.
2291877
,
2
.
2291878].
1
Due to a lack of space, only the rules that are used in the experimentations are given.
Search WWH ::
Custom Search