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 () instantiates only original variables and enforces AC on exactly the same set of variables of the double encoding as the corresponding algorithm hFC 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 () and hFC 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.
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 and , where and . All variables , , have domains . The allowed tuples of the constraints are and . If is given value 0 in the HVE then algorithms hFC2-hFC5 will prune tuples and from the domains of dual variables and 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.
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 variables, , each with domain , and constraints:
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 at each node, while MAC in the double encoding can use PW-AC to enforce AC, which costs . Therefore, there is only a polynomial difference.
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.
Nikolaos Samaras 2005-11-09