Arc Consistency

We know that AC in the DE is strictly stronger than GAC in the non-binary representation and AC in the HVE [Stergiou WalshStergiou Walsh1999]. Since the DE is a binary CSP, one obvious way to apply AC is using a generic AC algorithm. The domain size of a dual variable corresponding to a $k-$ary constraint is $d^k$ in the worst case. Therefore, if we apply an optimal AC algorithm then we can enforce AC on one dual constraint with $O(d^{2k})$ worst-case complexity. In the DE of a CSP with $e$ constraints of maximum arity $k$ there are at most $e(e-1)/2$ binary constraints (when all pairs of dual variables share one or more original variables). Therefore, we can enforce AC in the DE of the CSP with $O(e^2d^{2k})$ worst-case complexity. This is significantly more expensive compared to the $O(ekd^k)$ complexity bound of GAC in the non-binary representation and AC in the HVE. Because of the very high complexity bound, AC processing in the DE is considered to be impractical, except perhaps for very tight constraints.

However, we will now show that AC can be applied in the DE much more efficiently. To be precise we can enforce AC on the DE of a non-binary CSP with $O(e^3d^k)$ worst-case time complexity. The improvement in the asymptotic complexity can be achieved by exploiting the structure of the DE; namely, the fact that the constraints in the DE are piecewise functional.

Consider a binary constraint between dual variables $v_i$ and $v_j$. We can create a piecewise decomposition of the tuples in the domain of either dual variable into groups such that all tuples in a group are supported by the same group of tuples in the other variable. If the non-binary constraints corresponding to the two dual variables share $f$ original variables $x_1,\ldots ,x_f$ of domain size $d$, then we can partition the tuples of $v_i$ and $v_j$ into $d^f$ groups. Each tuple in a group $s$ includes the same sub-tuple of the form $(a_1,\ldots ,a_f)$, where $a_1\in D(x_1),\ldots ,a_f\in D(x_f)$. Each tuple $\tau$ in $s$ will be supported by all tuples in a group $s'$ of the other variable, where each tuple in $s'$ also includes the sub-tuple $(a_1,\ldots ,a_f)$.The tuples belonging to $s'$ will be the only supports of tuple $\tau$ since any other tuple does not contain the sub-tuple $(a_1,\ldots ,a_f)$. In other words, a group of tuples $s$ in variable $v_i$ will only be supported by a corresponding group $s'$ in variable $v_j$ where the tuples in both groups have the same values for the original variables that are common to the two encoded non-binary constraints. Therefore, the constraints in the DE are piecewise functional.

Example 4.1   Assume that we have two dual variables $v_1$ and $v_2$. $v_1$ encodes constraint $(x_1,x_2,x_3)$, and $v_2$ encodes constraint $(x_1,x_4,x_5)$, where the original variables
$x_1,\ldots,x_5$ have the domain $\{0,1,2\}$. We can partition the tuples in each dual variable into 3 groups. The first group will include tuples of the form $(0,*,*)$, the second will include tuples of the form $(1,*,*)$, and the third will include tuples of the form $(2,*,*)$. A star $(*)$ means that the corresponding original variable can take any value. Each group is supported only by the corresponding group in the other variable. Note that the tuples of a variable $v_i$ are partitioned in different groups according to each constraint that involves $v_i$. For instance, if there is another dual variable $v_3$ encoding constraint $(x_6,x_7,x_3)$ then the partition of tuples in $D(v_1)$ according to the constraint between $v_1$ and $v_3$ is into groups of the form $(*,*,0)$, $(*,*,1)$, $(*,*,2)$.

Van Hentenryck, Deville & Teng vhdt92 have shown that AC can be achieved in a set of binary piecewise functional constraints with $O(ed)$ worst-case time complexity, an improvement of $O(d)$ compared to the $O(ed^2)$ complexity of arbitrary binary constraints [Van Hentenryck, Deville, TengVan Hentenryck et al.1992]. Since we showed that the constraints in the DE are piecewise functional, the result of Van Hentenryck et al. vhdt92 means that we can improve on the $O(e^2d^{2k})$ complexity of AC in the DE.

Figure 4: PW-AC. An AC algorithm for the dual encoding.

In Figure 4 we sketch an AC-3 like AC algorithm specifically designed for the DE, which we call PW-AC ( PieceWise Arc Consistency). As we will show, this algorithm has a worst-case time complexity of $O(e^3d^k)$. The same complexity bound can be achieved by the AC-5 algorithm of Van Hentenryck et al. vhdt92, in its specialization to piecewise functional constraints, with the necessary adaptations to operate in the DE. As do most AC algorithms, PW-AC uses a stack (or queue) to propagate deletions from the domains of variables. This stack processes groups of piecewise decompositions, instead of variables or constraints as is usual in AC algorithms. We use the following notation:

• $S(v_i,v_j)=\{s_{1}(v_i,v_j),\ldots,s_{m}(v_i,v_j)\}$ denotes the piecewise decomposition of $D(v_i)$ with respect to the constraint between $v_i$ and $v_j$. Each $s_{l}(v_i,v_j)$, $l=1,\ldots,m$, is a group of the partition.

• $sup(s_{l}(v_i,v_j))$ denotes the group of $S(v_j,v_i)$ that can support group $s_{l}(v_i,v_j)$ of $S(v_i,v_j)$. As discussed, this group is unique.

• $counter(s_{l}(v_i,v_j))$ holds the number of valid tuples that belong to group $s_{l}(v_i,v_j)$ of decomposition $S(v_i,v_j)$. That is, at any time the value of $counter(s_{l}(v_i,v_j))$ gives the current cardinality of the group.

• $GroupOf(S(v_i,v_j),\tau)$ is a function that returns the group of $S(v_i,v_j)$ where tuple $\tau$ belongs. To implement this function, for each constraint between dual variables $v_i$ and $v_j$ we store the original variables shared by the non-binary constraints $c_{v_i}$ and $c_{v_j}$. Also, for each such original variable $x_l$ we store $pos(x_l,c_{v_i})$ and $pos(x_l,c_{v_j})$. In this way the $GroupOf$ function takes constant time.

• The set $\delta$ contains the groups that have their counter reduced to 0 after a call to function $Revise$. That is, groups such that all tuples belonging to them have been deleted.

The algorithm works as follows. In an initialization phase, for each group we count the number of tuples it contains (lines 3-6). Then, for each variable $v_i$ we iterate over the variables $v_j$ that are constrained with $v_i$. For each group $s_{l}(v_i,v_j)$ of $S(v_i,v_j)$, we check if $s_{l}(v_i,v_j)$ is empty or not (line 10). If it is empty, it is added to the stack for propagation.

In the next phase, function $Propagation$ is called to delete unsupported tuples and propagate the deletions (line 12). Once the previous phase has finished, the stack will contain a number of groups with 0 cardinality. For each such group $s_{l}(v_i,v_j)$ we must remove all tuples belonging to group $sup(s_{l}(v_i,v_j))$ since they have lost their support. This is done by successively removing a group $s_{l}(v_i,v_j)$ from the stack and calling function $Revise$. Since group $sup(s_{l}(v_i,v_j))$ has lost its support, each tuple $\tau\in D(x_j)$ that belongs to $sup(s_{l}(v_i,v_j))$ is deleted (lines 20-21). Apart from $sup(s_{l}(v_i,v_j))$, tuple $\tau$ may also belong to other groups that $D(v_j)$ is partitioned in with respect to constraints between $v_j$ and other variables. Since $\tau$ is deleted, the counters of these groups must be updated (i.e. reduced by one). This is done in lines 22-23. In the implementation we use function $GroupOf$ to access the relevant groups. If the counter of such a group becomes 0 then the group is added to the stack for propagation (lines 24-25 and 18). The process stops when either the stack or the domain of a variable becomes empty. In the former case, the DE is AC, while in the latter it is not.

The following example illustrates the advantage of algorithm PW-AC over both a generic AC algorithm employed in the DE, and AC in the HVE (or GAC in the non-binary representation).

Example 4.2   Consider three constraints $c_1$, $c_2$, $c_3$ as part of a CSP, where $vars(c_1)=\{x_0,x_1,x_3\}$, $vars(c_2)=\{x_2,x_3,x_4\}$, $vars(c_3)=\{x_2,x_4,x_5\}$. Assume that at some point the domains of the variables in the DE of the problem are as shown in Figure 5 (disregarding the original variables depicted with dashed lines).

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

=3.0in

Assume that we try to enforce AC in the DE using algorithm AC-2001⁵. The algorithm will discover that the first tuple in $D(v_{c_2})$ has no support in $D(v_{c_3})$ (there is no tuple with $x_2=0$ and $x_4=0$) and will delete it. Because of this deletion, the first two tuples in $D(v_{c_1})$ lose their support in $D(v_{c_2})$ and AC-2001 must therefore look for new supports. For each of the two tuples of $D(v_{c_1})$ the algorithm will check all the 6 remaining tuples in $D(v_{c_2})$ before discovering that there is no support. As a result the two tuples will be deleted. Algorithm PW-AC, on the other hand, will set the counter of the group where the first tuple of $D(v_{c_2})$ belongs (according to partition $S(v_{c_2},v_{c_3})$) to 0 once it deletes the tuple. This will result in a call to function $Revise$ and an automatic deletion of the first two tuples of $D(v_{c_1})$, saving a total of $2\times 6$ checks.

Now consider the HVE of the problem. Applying AC on the HVE will have no effect because values 0 and 1 of $x_2$ and $x_4$ are both supported in $D(v_{c_2})$ and $D(v_{c_3})$. Therefore there is no propagation through these variables, and as a result the two tuples of $D(v_{c_1})$ will not be deleted. Similarly, there will be no propagation if we apply GAC in the non-binary representation of the problem.

Note that the theoretical results regarding the DE presented in the rest of the paper hold if the AC-5 algorithm of Van Hentenryck et al. vhdt92 was adapted and used the DE instead of PW-AC. The two algorithms have some similarities (e.g. they both use a function to access the group of a decomposition that a certain tuple belongs to, though implemented differently), but their basic operation is different. The algorithm of Van Hentenryck et al. vhdt92, being an instantiation of AC-5, handles a queue of triples $(v_i,v_j,a)$ to implement constraint propagation, where $v_i$ and $v_j$ are two variables involved in a constraint and $a$ is a value that has been removed from $D(v_j)$. PW-AC utilizes a queue of piecewise decompositions. Also the data structures used by the algorithms are different. PW-AC checks and updates counters to perform the propagation which, as we explain below, requires space exponential in the number of common variables in the non-binary constraints. The algorithm of Van Hentenryck et al. vhdt92 utilizes a more complicated data structure which requires space exponential in the arity of the non-binary constraints. It has to be noted, however, that PW-AC is specifically designed for the DE. That is, its operation, data structures, and the way it checks for consistency are based on the fact that the domains of the dual variables consist of the tuples of the original constraints extensionally stored. On the other hand, the algorithm of Van Hentenryck et al. vhdt92 is generic, in the sense that it can be adapted to operate on any piecewise functional constraint.