Arc Consistency in Binary Encodings of Non-binary CSPs: Theoretical and Experimental Evaluation

摘要

A Non-binary Constraint Satisfaction Problem (CSP) can be solved by converting the problem into an equivalent binary one and applying well-established binary CSP techniques. An alternative way is to use extended versions of binary techniques directly on the non-binary problem. There are two well-known computational methods in the literature for translating a non-binary CSP to an equivalent binary CSP; (ⅰ) the hidden variable encoding and (ⅱ) the dual encoding. In this paper we make a theoretical and empirical study of arc consistency for the binary encodings. An arc consistency algorithm for the hidden variable encoding with optimal O(ekd~k) worst-case time complexity is presented. This algorithm is compared theoretically and empirically to an optimal generalized arc consistency algorithm that operates on the non-binary representation. We also describe an arc consistency algorithm for the dual encoding with O(e~2d~k) worst-case complexity. This gives an O(d~k) reduction compared to a generic arc consistency algorithm. Both theoretical and computational results show that the encodings are competitive with the non-binary representation for certain classes of non-binary CSPs.