Dual Encoding

The dual encoding (originally called dual graph encoding) was inspired by work in relational databases. In the dual encoding (DE) [Dechter PearlDechter Pearl1989] the variables are swapped with constraints and vice versa. Each constraint $c$ of the original non-binary CSP is represented by a variable which we call a dual variable and denote by $v_c$. We refer to the variables of the original non-binary CSP as original variables. The domain of each dual variable $v_c$ consists of the set of allowed tuples in the original constraint $c$. Binary constraints between two dual variables $v_c$ and $v_{c'}$ exist iff $vars(c)\cap vars(c')\neq \emptyset$. That is, iff the constraints $c$ and $c'$ share one or more original variables. If $common\_vars$ is the set of original variables common to $c$ and $c'$ then a tuple $\tau \in D(v_c)$ is supported in the constraint between $v_c$ and $v_{c'}$ iff there exists a tuple $\tau'\in D(v_{c'})$ such that $\tau[common\_vars]=\tau'[common\_vars]$.

Figure 1: Dual encoding of a non-binary CSP.

=2.5in

Consider the following example with six variables with 0-1 domains, and four constraints: $c_1:\ x_1+x_2+x_6 = 1$, $c_2:\ x_1-x_3+x_4 = 1$, $c_3:\ x_4+x_5-x_6 \geq 1$, and $c_4:\ x_2+x_5-x_6 = 0$. The DE represents this problem with 4 dual variables, one for each constraint. The domains of these dual variables are the tuples that satisfy the respective constraint. For example, the dual variable $v_{c_3}$ associated with the third constraint has the domain $\{ (0,1,0), (1,0,0), (1,1,0), (1,1,1)\}$ as these are the tuples of values for $(x_4,x_5,x_6)$ which satisfy $x_4+x_5-x_6 \geq 1$. As a second example, the dual variable $v_{c_4}$ associated with the last constraint has the domain $\{ (0,0,0), (0,1,1), (1,0,1) \}$. Between $v_{c_3}$ and $v_{c_4}$ there is a compatibility constraint to ensure that the two original variables in common, $x_5$ and $x_6$, have the same values. This constraint allows only those pairs of tuples which agree on the second and third elements (i.e. $(1,0,0)$ for $v_{c_3}$ and $(0,0,0)$ for $v_{c_4}$, or $(1,1,1)$ for $v_{c_3}$ and $(0,1,1)$ for $v_{c_4}$). The DE of the problem is shown in Figure 1.

In the rest of this paper, we will sometimes denote by $c_{v_i}$ the non-binary constraint that is encoded by dual variable $v_i$. For an original variable $x_j\in vars(c_{v_i})$, $pos(x_j,c_{v_i})$ will denote the position of $x_j$ in $c_{v_i}$. For instance, given a constraint $c_{v_i}$ on variables $x_1,x_2,x_3$, $pos(x_2,c_{v_i})=2$.