Algorithms for the Double Encoding

The double encoding has rarely been used in experiments with binary encodings, although it combines features of the HVE and the DE, and therefore may exploit the advantages of both worlds. To be precise, the double encoding offers the following interesting potential: search algorithms can deploy dynamic variable ordering heuristics to assign values to the original variables, while constraint propagation can be implemented through the constraints between dual variables to achieve higher pruning. In this section we first briefly discuss how AC can be applied in the double encoding. We then show how various search algorithms can be adapted to operate in the double encoding.