Constraint inference explained
In constraint satisfaction, constraint inference is a relationship between constraints and their consequences. A set of constraints
entails a constraint
if every solution to
is also a solution to
. In other words, if
is a valuation of the variables in the scopes of the constraints in
and all constraints in
are satisfied by
, then
also satisfies the constraint
.
Some operations on constraints produce a new constraint that is a consequence of them. Constraint composition operates on a pair of binary constraints
and
with a common variable. The composition of such two constraints is the constraint
that is satisfied by every evaluation of the two non-shared variables for which there exists a value of the shared variable
such that the evaluation of these three variables satisfies the two original constraints
and
.
Constraint projection restricts the effects of a constraint to some of its variables. Given a constraint
its projection to a subset
of its variables is the constraint
that is satisfied by an evaluation if this evaluation can be extended to the other variables in such a way the original constraint
is satisfied.
Extended composition is similar in principle to composition, but allows for an arbitrary number of possibly non-binary constraints; the generated constraint is on an arbitrary subset of the variables of the original constraints. Given constraints
and a list
of their variables, the extended composition of them is the constraint
where an evaluation of
satisfies this constraint if it can be extended to the other variables so that
are all satisfied.
See also
References
- Book: Dechter
, Rina
. Constraint processing. Morgan Kaufmann. 2003.
- Book: Apt
, Krzysztof
. Krzysztof R. Apt. Principles of constraint programming. Cambridge University Press. 2003.
- Book: Marriott
, Kim
. Peter J. Stuckey. Programming with constraints: An introduction. 1998. MIT Press.
