Binary Encodings of Non-binary Constraint Satisfaction Problems:
  Algorithms and Experimental Results
  A non-binary Constraint Satisfaction Problem (CSP) can be solved directly
using extended versions of binary techniques. Alternatively, the non-binary
problem can be translated into an equivalent binary one. In this case, it is
generally accepted that the translated problem can be solved by applying
well-established techniques for binary CSPs. In this paper we evaluate the
applicability of the latter approach. We demonstrate that the use of standard
techniques for binary CSPs in the encodings of non-binary problems is
problematic and results in models that are very rarely competitive with the
non-binary representation. To overcome this, we propose specialized arc
consistency and search algorithms for binary encodings, and we evaluate them
theoretically and empirically. We consider three binary representations; the
hidden variable encoding, the dual encoding, and the double encoding.
Theoretical and empirical results show that, for certain classes of non-binary
constraints, binary encodings are a competitive option, and in many cases, a
better one than the non-binary representation.
