Information Technology Reference
In-Depth Information
x
2
g
1
10
g
2
0
x
1
0
1
Fig. 1.
Slow convergence in constraint propagation.
4
Implementation and Results
An implementation has been realized in
. In the following we give
details of the encoding of constraint projections. In order to illustrate the effects
of our approach in consistency reasonings, a set of experimental results is also
discussed.
RealPaver
4.1
Implementation Details
First of all let us note that every constraint can be expressed as a projection
constraint:
f
= 0 corresponds to
f
∈
[0
,
0] and
f
0to
f
∈
[
−∞
,
0]. Projec-
tions on terms are computed by the
algorithm, which is a chain rule
enforcing elementary constraint inversion steps [7].
HC4revise
Example 5.
Let
f
be a term and let
C
be the constraint (
f
+
y
)
−
1=0.Given
10
,
10]
2
the box [
−
let us implement
to compute an interval
I
such
HC4revise
that the projection constraint
f
∈
I
holds. Constraint
C
is rewritten as the
projection constraint (
f
+
y
)
−
1
∈
[0
,
0]. The first inversion step eliminates the
minus operation:
f
+
y
∈
[0
,
0] + 1 = [1
,
1]. The second inversion step removes
the plus operation:
f
∈
[1
,
1]
−
y
and
y
is replaced with its domain:
f
∈
−
9
,
11].
[
Now, given the constraint
f
∈
−
9
,
11] box consistency may be enforced over
f
.
[
Giventwoprojectionconstraints
f
∈
I
and
g
∈
J
every redundant constraint
ψ
(
ϕ
(
f, g
))
φ
I
(
I,J
) is represented as follows. Term
ψ
(
ϕ
(
f, g
)) is represented in
explicit form in the DAG.
φ
I
(
I,J
) is implemented as an interval function taking
as input the intervals
I
and
J
available at the root nodes of
f
and
g
in the
DAG. This function is located in the root node of term
ψ
(
ϕ
(
f, g
)). This way
φ
I
is evaluated as fast as possible and memory consumption is kept in reasonable
bounds. If the expression of
ψ
(
ϕ
(
f, g
)) is simple then the computation of box
consistency may be precise and cheap.
∈
Search WWH ::
Custom Search