Algorithms for the double encoding demonstrate especially promising performance. When many non-binary constraints that share more than one variable are present in a problem then MAC in the double encoding can exploit the benefits of both the variable ordering heuristic, borrowed from the non-binary representation, and the stronger filtering, borrowed from the DE, to outperform the other representations. This was demonstrated in problems with such structure (random and also frequency assignment - like). This is also the case in the ``still-life'' problem, which explains the success of the double encoding10. In addition, the double encoding offers the interesting potential of hybrid models where certain constraints are encoded into binary and others are kept in the non-binary representation based on certain properties of the constraints. To be precise we can benefit by encoding constraints that are either naturally specified in extension, or have relatively low arity and are tight. This was demonstrated in various domains. Most notably, in the frequency assignment problems where the double encoding (or a hybrid one) payed off in most cases, although the constraints in such problems are naturally defined intentionally.
Nikolaos Samaras 2005-11-09