Experimental Results

In this section we make an empirical study of algorithms for binary encodings. The empirical study is organized in two parts:

• In the first part (Subsections 6.1 and 6.2) we evaluate the improvements offered by specialized algorithms compared to generic ones. At the same time we compare the efficiency of algorithms that run in the binary encodings to their non-binary counterparts. This comparison can give us a better understanding of when encoding a non-binary problem into a binary one pays off, and which encoding is preferable. For this empirical investigation we use randomly generated problems, random problems with added structure, and benchmark crossword puzzle generation problems. Random problems allow us to relate the performance of the algorithms to certain parameters, such as tightness, constraint graph density, and domain size. Crossword puzzles are standard benchmarks for comparing binary to non-binary constraint models, and allow us to to evaluate the performance of the algorithms on problems that include constraints of high arity.

• In the second part (Subsection 6.3) , we investigate the usefulness of binary encodings in more realistic problem settings. For this study we use problems from the domains of configuration and frequency assignment and we compare the performance of MAC algorithms that run in the encodings to an MGAC algorithm in the non-binary representation.

All algorithms were implemented in C. All experiments were run on a PC with a 3.06 GHz Pentium 4 processor and 1 GB RAM. In all experiments, all algorithms use the dom/deg heuristic [Bessière RéginBessière Régin1996b] for dynamic variable ordering and lexicographic value ordering.