AC can be enforced on the double encoding using algorithm PW-AC with the addition that each time a value of an original variable loses all its supports in an adjacent dual variable, it is deleted from . 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.
Nikolaos Samaras 2005-11-09