Arc Consistency

AC can be enforced on the double encoding using algorithm PW-AC with the addition that each time a value $a$ of an original variable $x_i$ loses all its supports in an adjacent dual variable, it is deleted from $D(x_i)$. Alternatively, we can use any generic AC algorithm, such as AC-2001. Note that an AC algorithm applied in the double encoding can enforce various levels of consistency depending on which constraints it uses for propagation between dual variables. That is, propagation can be either done directly through the constraints between dual variables, or indirectly through the constraints between dual and original variables. For example, if we only use the constraints between dual and original variables then we get the same level of consistency as AC in the HVE. If propagation between dual variables is performed using the constraints of the DE then we get the same level of consistency as AC in the DE, for the dual variables, and we also prune the domains of the original variables. In between, we have the option to use different constraints for propagation in different parts of the problem. As the next example shows, AC in the double encoding can achieve a very high level of consistency compared to the non-binary representation. In Sections 6.2 and 6.3 we will show that this can have a profound effect in practice.

Example 5.1   Consider the problem of Figure 6. Applying AC through the constraint between the two dual variables will determine that the problem is insoluble. However, the problem in its non-binary representation is not only GAC, but also singleton (generalized) arc consistent (SGAC), which is a very high level of consistency. A CSP is SGAC if after applying GAC in the problem induced by any instantiation of a single variable, there is no domain wipeout [Debruyne BessièreDebruyne Bessière2001,Prosser, Stergiou, WalshProsser et al.2000].

Figure 6: Double encoding of a problem that is not AC in the double encoding but is SGAC in the non-binary representation.

=3.0in