Information Technology Reference
In-Depth Information
Informally speaking, each box containing a solution of
C
in
must be included
in the interval relation. As a consequence, the approximation does not lose any
solution. Methods based on constraint satisfaction in
Σ
I
are said to be
complete
.
R
Notations.
Given a box
D
and a term
f
(resp. a constraint
C
) such that each of
its variables has a domain in
D
,let
D
|f
(resp.
D
|C
) be the restriction of
D
to the
variables of
f
(resp.
C
). In the following, we will simply write
f
I
(
D
)(
D
∈
C
I
)
for
f
I
(
D
|f
)(resp.
D
|C
∈
C
I
).
2.3
Numeric Constraints
A
numerical constraint satisfaction problem
(NCSP) is given by a conjunction
of constraints
F
(
x
1
,...,x
n
)oftheform:
C
1
∧ ···∧
C
m
∧
x
1
a
1
∧
x
1
b
1
∧···∧
x
n
a
n
∧
x
n
b
n
NCSPs can be solved by a bisection algorithm, which maintains a set of boxes.
The initial box is given by the variable domains. Boxes are processed by split-
ting and narrowing operations. A splitting step transforms a box into a set of
smaller boxes whose union is equivalent. A narrowing operation reduces a box
by removing facets that are solution-free. The output is a set of boxes whose
union is a superset of the set of solutions of the NCSP.
2.4
Narrowing
A basic narrowing procedure consists in using constraint satisfaction in the in-
terval structure. Given a box, if at least one constraint is not satisfied then the
whole NCSP cannot be satisfied. By Theorem 2, it follows that it cannot be
satisfied in the real structure. As a consequence, the box can be rejected. Unfor-
tunately this method is weak since a free-solution space needs to be completely
isolated by splitting before being eliminated.
A more powerful approach is based on constraint projections. In the con-
straint programming literature [12], projections have been defined to determine
the allowed values of one variable in order to satisfy one constraint in the real
domain. More precisely, given a constraint
C
(
x
1
,...,x
n
), a box
D
n
and a
variable
x
i
occurring in
C
,the
projection
of
C
on
x
i
in
D
is the set of real
numbers
∈
I
Π
x
i
(
C, D
)=
{
a
i
∈
D
i
|∃
a
1
∈
D
1
,...,
∃
a
i−
1
∈
D
i−
1
,
∃
a
i
+1
∈
D
i
+1
,...,
∃
a
n
∈
D
n
:
(
a
1
,...,a
n
)
∈
C
R
}
.
The definition of projections is naturally extended to conjunctions of constraints
by considering that all constraints have to be satisfied. In most solving engines of
existing solvers, only one constraint is used during a narrowing operation. That
leads to the
locality problem
, which is the main concern of our work. Given a
Search WWH ::
Custom Search