Dual and Double Encodings

The DE and the double encoding have the advantage of strong filtering through the constraints between dual variables. We showed that this advantage can be exploited by a low cost specialized algorithm, such as PW-AC, to make the DE competitive and often significantly better than the non-binary representation in several sparse CSPs, such as crossword puzzle generation and configuration problems. For dense CSPs, the DE does not pay off because either the spatial requirements make its use infeasible, or if this is not the case, the advantages offered are outweighed by the overhead of updating the domains of dual variables. The same holds for CSPs containing constraints of large arity unless they are very tight (as in crossword puzzles).

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¹⁰. 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.