Conclusion

In this paper we studied three binary translations of non-binary CSPs; the hidden variable encoding, the dual encoding, and the double encoding. We showed that the common perception that standard algorithms for binary CSPs can be used in the encodings of non-binary CSPs suffers from flaws. Namely, standard algorithms do not exploit the structure of the encodings, and end up being inefficient. To address this problem, we proposed specialized arc consistency and search algorithms for the encodings, and we evaluated them theoretically and empirically. We showed how arc consistency can be enforced on the hidden variable encoding of a non-binary CSP with the same worst-case time complexity as generalized arc consistency on the non-binary representation. We showed that the structure of constraints in the dual encoding can be exploited to achieve a much lower time complexity than a generic algorithm. Empirical results demonstrated that the use of a specialized algorithm makes the dual encoding significantly more efficient. We showed that generalized search algorithms for non-binary CSPs can be relatively easily adjusted to operate in the hidden variable encoding. We also showed how various algorithms for the double encoding can be designed. These algorithms can exploit the properties of the double encoding (strong filtering and branching on original variables) to achieve very good results in certain problems. Empirical results in random and structured problems showed that, for certain classes of non-binary constraints, using binary encodings is a competitive option, and in many cases, a better one than solving the non-binary representation.