Information Technology Reference
In-Depth Information
reaching quiescence. Unfortunately, these techniques may be weak, since some
constraint projection may be less precise than the projection of the solution set.
The locality problem of projection-based reasonings can be handled in sev-
eral ways, one of which being the symbolic combination of constraints [1]. The
purpose is to eliminate variables in order to concentrate global information of
the system in a smaller set of variables. As a consequence, local reasoning over
the new constraints may derive global information. In this paper, we propose to
improve consistency reasonings by means of redundant constraints [16], as shown
in the following example (which is very simple for the sake of comprehension).
Example 1.
Let
x
and
y
be two variables lying in the real interval [
−
10
,
10].
Consider the following constraint systems:
P
=
xy
=1
xy
=2
P
=
xy
=1
xy
sin(
y
)=2
It is worth noticing that variable domains cannot be reduced using projections,
e.g.
, for every value of
x
(take
x
= 2), there exists a value of
y
such that
xy
=1
(here
y
=0
.
5). The same conclusions are obtained for
y
and the second con-
straint. However, these problems are not satisfiable, which can be easily verified.
The term
xy
is equal to two terms in
P
, whose evaluations are not compatible
(1
= 2). As a consequence,
P
is not satisfiable. The division of the left-hand
terms of equations from
P
must be equal to the division of right-hand terms.
Now simplify the result to derive sin(
y
) = 2. Since a sine cannot be greater than
1, then
P
is not satisfiable.
Example 1 shows that the combination of terms introduces more global reason-
ings in the process of solving nonlinear constraint systems. The first, well-known,
idea is to share projections on terms, not only on variables. The second idea is
to combine terms using symbolic transformations. This approach can be seen as
a form of microscopic redundant computations, which may work for equations
or inequalities. Since nonlinear constraints cannot be simplified in general, only
well-chosen terms have to be combined.
In the following, we will focus on box consistency [2], the local consistency
technique implemented in
[17]. Box consistency is a basis for approx-
imating constraint projections using interval numbers. The first contribution
of this paper is the generalization of the definition of box consistency to pro-
cess projections on terms. The second contribution is the combination technique
used to generate redundant constraints that may improve box consistency. An
implementation has been done in
Numerica
[6]. Encouraging experimental re-
sults have been obtained on a set of known problems from different application
domains.
The rest of this paper is organized as follows. Section 2 presents the basics
related to numerical constraints and interval constraint solving. The main con-
tributions are introduced in Section 3. The experimental results are discussed
in Section 4. Last, Section 5 summarizes the contributions and points out some
directions for future research.
RealPaver
Search WWH ::
Custom Search