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.