Functional and Piecewise Functional Constraints

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 $c$, where $vars(c)=\{x_i,x_j\}$, is functional with respect to $D(x_i)$ and $D(x_j)$ iff for all $a\in D(x_i)$ (resp. $b\in D(x_j)$) there exists at most one value $b\in D(x_j)$ (resp. $a\in D(x_i)$) such that $b$ is a support of $a$ in $c$ (resp. $a$ is a support of $b$).

An example of a functional constraint is $x_i=x_j$. 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 $x_{i}$, $x_{j}$ is a constraint where the domains of $x_i$ and $x_j$ can be partitioned into groups such that each group of $D(x_i)$ is supported by at most one group of $D(x_j)$, and vice versa. To give a formal definition, we first define the concept of a piecewise decomposition.

Definition 2.3   [Van Hentenryck, Deville, TengVan Hentenryck et al.1992] Let $c$ be a binary constraint with $vars(c)=\{x_i,x_j\}$. The partitions $S=\{s_{1},\ldots,s_{m}\}$ of $D(x_i)$ and $S'=\{s'_{1},\ldots,s'_{m'}\}$ of $D(x_j)$ are a piecewise decomposition of $D(x_i)$ and $D(x_j)$ with respect to $c$ iff for all $s_l\in S$,$s'_{l'}\in S'$, the following property holds: either for all $a\in s_l$, $b\in s'_{l'}$, $(a,b)\in rel(c)$, or for all $a\in s_l$, $b\in s'_{l'}$, $(a,b)\notin rel(c)$.

Definition 2.4   [Van Hentenryck, Deville, TengVan Hentenryck et al.1992] A binary constraint $c$, where $vars(c)=\{x_i,x_j\}$, is piecewise functional with respect to $D(x_i)$ and $D(x_j)$ iff there exists a piecewise decomposition $S=\{s_{1},\ldots,s_{m}\}$ of $D(x_i)$ and $S'=\{s'_{1},\ldots,s'_{m'}\}$ of $D(x_j)$ with respect to $c$ such that for all $s_l\in S$ (resp. $s'_{l'}\in S'$), there exists at most one $s'_{l'}\in S'$ (resp. $s_{l}\in S$), such that for all $a\in s_l$, $b\in s'_{l'}$ $(a,b)\in rel(c)$.

Example of piecewise functional constraints are the modulo ($x_2$ MOD $x_3$ = $a$) and integer division ($x_2$ DIV $x_3$ = $a$) constraints.