Search Algorithms

Various search algorithms for the double encoding can be defined, depending on the variables that are instantiated and the constraints that are used for propagation. Here we will restrict ourselves to algorithms that only instantiate original variables and perform propagation using the constraints between dual variables. Intuitively this is the most interesting class of algorithms because they combine nice features from the non-binary representation and the HVE (small domain sizes), and from the DE (strong propagation).

We first show that the FC versions for the HVE discussed in Section 3.2 can be adapted to yield algorithms that run on the double encoding. We call these algorithms dFC0-dFC5. Each algorithm dFC$i$ ($i=0,\ldots,5$) instantiates only original variables and enforces AC on exactly the same set of variables of the double encoding as the corresponding algorithm hFC$i$ does in the HVE. For example, dFC5 will enforce AC on the set of dual variables, and original variables connected to them, such that each dual variable is connected to at least one past original variable and at least one future original variable. The difference between algorithm dFC$i$ ($i=2,\ldots,5$) and hFC$i$ is that the former can exploit the constraints between dual variables to enforce a higher level of consistency than the latter. Not surprisingly, this results in stronger algorithms.

Proposition 5.1   In any non-binary CSP, under a fixed variable and value ordering, algorithm dFCi (i$=2,\ldots,5$) is strictly stronger than the respective algorithm hFCi.

Proof: It is easy to see that if a value is pruned by hFCi in the HVE then it is also pruned by dFCi in the double encoding. This is a straightforward consequence of the fact that 1) the double encoding subsumes the HVE, and 2) algorithms dFCi and hFCi enforce AC on the same set of variables. Algorithm dFCi is strictly stronger than hFCi because, by exploiting the constraints between dual variables, it can prune more values than hFCi. Consider, for instance, a problem with two constraints $c_1$ and $c_2$, where $vars(c_1)=\{x_1,x_2,x_3,x_4\}$ and $vars(c_2)=\{x_1,x_2,x_3,x_5\}$. All variables $x_i$, $i=1,\ldots, 5$, have domains $\{0,1\}$. The allowed tuples of the constraints are $rel(c_1)=\{(0,0,1,0),(0,1,0,1),(1,1,0,1)\}$ and $rel(c_2)=\{(0,0,0,0),(0,1,1,1),(1,0,0,0)\}$. If $x_1$ is given value 0 in the HVE then algorithms hFC2-hFC5 will prune tuples $(1,1,0,1)$ and $(1,0,0,0)$ from the domains of dual variables $v_{c_1}$ and $v_{c_2}$ respectively. No other pruning will be performed. In the double encoding, the same variable assignment, by any of the algorithms dFC2-dFC5, will cause the domain wipe-out of the two dual variables. $\Box$

Corollary 5.1   In any non-binary CSP, under a fixed variable and value ordering, algorithm dFCi (i$=2\ldots 5$) is strictly stronger than the respective algorithm nFCi (i=$2\ldots 5$).

Proof: Straightforward consequence of Propositions 5.1 and 3.1. $\Box$

It is easy to see that algorithm hFC0 (i.e. simple binary FC) is equivalent to dFC0. The same holds for algorithms hFC1 and dFC1. As with the various versions of FC, the MAC algorithm can be adapted to run in the the double encoding so that only original variables are instantiated, and propagation is implemented through the constraints between dual variables. It is easy to see that this algorithm is strictly stronger than the corresponding algorithm for the HVE (the proof is similar to the proof of Proposition 5.1). More interestingly, we show that this MAC algorithm for the double encoding can, at most, have a polynomially greater cost than the corresponding MAC algorithm for the HVE, while, on the other hand, it can be exponentially better.

Proposition 5.2   In any non-binary CSP, under a fixed variable and value ordering, the MAC algorithm for the hidden variable encoding that only instantiates original variables can have exponentially greater cost than the corresponding MAC algorithm for the double encoding.

Proof: To prove this, we can use Example 14 from the paper by Bacchus et al. bcvbw02. In this example we have a CSP with $4n+2$ variables, $x_1,\ldots,x_{4n+2}$, each with domain $\{1,\ldots,n\}$, and $2n+1$ constraints:

$c_1$: $(x_1+x_2\ mod\ 2) \neq (x_3+x_4\ mod\ 2)$

$c_2$: $(x_3+x_4\ mod\ 2) \neq (x_5+x_6\ mod\ 2)$

$\ldots$

$c_{2n}$: $(x_{4n-1}+x_{4n}\ mod\ 2) \neq (x_{4n+1}+x_{4n+2}\ mod\ 2)$

$c_{2n+1}$: $(x_{4n+1}+x_{4n+2}\ mod\ 2) \neq (x_1+x_2\ mod\ 2)$

Assume that the variables are assigned in lexicographic order in the double encoding. If $x_1$ and $x_2$ are assigned values such that $(x_1+x_2\ mod\ 2)=0$ then enforcing AC will prune any tuples from $D(v_{c_1})$ such that $(x_3+x_4\ mod\ 2)=0$. This in turn will prune from $D(v_{c_2})$ any tuples such that $(x_5+x_6\ mod\ 2)=1$. Continuing this way, AC propagation will prune from $D(v_{c_{2n+1}})$ any values such that $(x_1+x_2\ mod\ 2)=0$. When these deletions are propagated to $v_{c_1}$, $D(v_{c_1})$ will become empty. In a similar way, enforcing AC after assignments to $x_1$ and $x_2$, such that $(x_1+x_2\ mod\ 2)=1$, leaves $D(v_{c_1})$ empty. Therefore, the CSP is insoluble. MAC in the double encoding needs to instantiate two variables to discover this, and visit $O(n^2)$ nodes. On the other hand, as explained by Bacchus et al. bcvbw02, MAC in the HVE needs to visit $O(n^{log(n)})$ nodes to conclude that the problem is insoluble. Finally, note that, for each node, the asymptotic costs of MAC in the double encoding (using PW-AC) and MAC in the HVE are polynomially related. Therefore, MAC in the HVE can be exponentially worse than MAC in the double encoding. $\Box$

A corollary of Proposition 5.2 is that MAC in the double encoding can have have exponentially smaller cost than MGAC in the non-binary representation.

Proposition 5.3   In any non-binary CSP, under a fixed variable and value ordering, the MAC algorithm for the double encoding that only instantiates original variables can have at most polynomially greater cost than the corresponding MAC algorithm for the hidden variable encoding.

Proof: To prove this we need to show two things: 1) The number of node visits made by MAC in the double encoding is at most by a polynomial factor greater than the number of node visits made by MAC in the HVE, 2) At each node, the worst-case cost of MAC in the double encoding is at most by a polynomial factor greater than the worst-case cost of AC in the HVE. The former is true since MAC in the double encoding is strictly stronger than MAC in the HVE. The latter can be established by considering the worst case complexities of the algorithms at each node. MAC in the HVE costs $O(ekd^k)$ at each node, while MAC in the double encoding can use PW-AC to enforce AC, which costs $O(e^3d^k)$. Therefore, there is only a polynomial difference. $\Box$

In a similar way, we can prove that the relationship of Proposition 5.3 holds between each algorithm dFCi (i$=2\ldots 5$) and the corresponding algorithm hFCi. A corollary of Proposition 5.3 is that MAC in the double encoding can have at most polynomially greater cost than MGAC in the non-binary representation. It is important to note that Proposition 5.3 holds only if algorithm PW-AC is used to enforce AC in the double encoding. If we use a generic algorithm, like AC-2001, then we can get exponential differences in favor of MAC in the HVE. Finally, regarding the relationship in node visits among the algorithms for the double encoding, we have the following.

Proposition 5.4   Given the double encoding of a CSP with fixed variable and value ordering schemes, the following relations hold:

1. nodes(dFC1)$\subseteq$ nodes(dFC0)
2. nodes(dFC2)$\subseteq$ nodes(dFC1)
3. nodes(dFC5)$\subseteq$ nodes(dFC3)$\subseteq$ nodes(dFC2)
4. nodes(dFC5)$\subseteq$ nodes(dFC4)$\subseteq$ nodes(dFC2)
5. nodes(dMAC)$\subseteq$ nodes(dFC5)

Proof: The proof is very simple and it is based on comparing the size of the subsets of the problem where each algorithm enforces AC. $\Box$