Dual and Double Encodings

In this empirical study we investigated the performance of algorithms for the DE and double encoding. We tried to answer the following three questions: 1) How efficient are specialized algorithms compared to generic algorithms? 2) Does the use of a specialized algorithm make the DE an effective option for solving non-binary CSPs? 3) Can we take advantage of the theoretical properties of the double encoding in practice? To answer these questions, we run experiments with random and structured problems to evaluate the benefits offered by the specialized algorithm PW-AC when maintaining AC during search. We compared the performance of two MAC algorithms; one that uses AC-2001 to enforce AC (MAC-2001), and another that uses PW-AC to enforce AC (MAC-PW-AC). We also compared these algorithms to an algorithm that maintains GAC in the non-binary representation using GAC-2001 (MGAC-2001), and to MAC algorithms that maintain AC in the double encoding using PW-AC (algorithm MAC-PW-ACd) and AC-2001 (algorithm MAC-2001d).