Information Technology Reference
In-Depth Information
are both not assigned, then merge them into one
variable node according to unit sharing strategy, check whether positive cycle
generates, and possibly simplify and check the consistency of inequality graph. If
the new node domain is smaller to some extent than the domain of
For r is =, If variable
x
and
y
x
or
y
, then
propagate the interval along inequality graph. If
are both assigned
variables or constants, then decide whether their values are equal; If there exists
only one unassigned variable and the value of another variable drops on this
unassigned variable domain, then assign the value to the unassigned variable and
propagate constraints; Otherwise, report the inconsistency.
For r is ≤, if variable
x
and
y
are already assigned, then decide whether ≤
relation is tenable; Otherwise, carry on consistency limit to the interval of
x
and
y
x
and
y
is smaller to some extent, then propagate the
interval along inequality graph. If these two variables are both not unassigned,
then add an edge with relation ≠ into this inequality graph, check whether
positive cycle generates, and possibly simplify and check the consistency of
inequality graph.
For r is ≠, if variable
. If the limited interval of the
x
or
y
x
and
y
are both already assigned, then decide whether ≠
relation is tenable.
For
x<y
,
x>y
and
x
≥
y
, their equivalent transformation are (
x
≤
y
)∧(
x
≠
y
) ,(
y
≤
x
respectively.
Inequality reasoner offers inquiry of inequality relation between any two
variables with the same type, even they are not assignment. The method which
combines symbol reasoning and interval propagation, is not only to regard
inequality as the internal predicate to reduce the reasoning cost, but also
eliminate the redundancy and reduce the solution scale of problem. Furthermore,
as a general inequality reasoner, it can carry on symbol reasoning before the
situation that variable is not assigned or even added interval limit. For example,
system can check the inequality set and find out {
)∧(
x
≠
y
) ,
y
≤
x
} contains
inconsistent. Inequality reasoning makes system have a function of propagating
partial relation. The function has been used widely in qualitative reasoning. By
realizing operations of equality and inequality reasoning, system increases the
reasoning depth, avoids more generated tests and thus reduces search space.
x
≤
y
,
y
≤
z
,
x>z
3.11 Constraint Reasoning System COPS
A main function of constraint reasoning system to offer common and effective
constraint reasoning mechanism for user. This reasoning mechanism should
