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
encoding^{10}. 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