The specialized AC algorithms for the hidden variable and the dual
encoding that we will describe in Sections 3
and 4 exploit structural properties of the encodings.
As we will explain in detail later, the binary constraints in the
hidden variable encoding are one-way functional, while the binary
constraints in the dual encoding are piecewise functional. We now
define these concepts.
Definition 2.2 A binary constraint
, where
, is
functional with respect to
and
iff for all
(resp.
) there exists at most one value
(resp.
) such that
is a support of
in
(resp.
is a support of
).
An example of a functional constraint is . A binary
constraint is one-way functional if the functionality
property holds with respect to only one of the variables involved
in the constraint.
Informally, a piecewise functional constraint over variables
, is a constraint where the domains of and
can be partitioned into groups such that each group of
is supported by at most one group of , and vice
versa. To give a formal definition, we first define the concept of
a piecewise decomposition.
Definition 2.4 [
Van Hentenryck, Deville, TengVan Hentenryck
et al.1992]
A binary constraint
, where
, is
piecewise functional with respect to
and
iff
there exists a piecewise decomposition
of
and
of
with
respect to
such that for all
(resp.
), there exists at most one
(resp.
), such that for all
,
.
Example of piecewise functional constraints are the modulo (
MOD = ) and integer division ( DIV = )
constraints.
Nikolaos Samaras
2005-11-09