Any search algorithm for binary CSPs can be used in the DE. Algorithm PW-AC can be easily embedded in a MAC algorithm. Experimental results presented in Section 6 will demonstrate that such an algorithm is by far more efficient than a MAC algorithm that uses a generic algorithm to apply AC. In many problems, this improvement makes MAC in the DE outperform MGAC in the non-binary representation.

It is important to note that apart from providing an efficient way
to enforce AC in the DE, the PW-AC algorithm can also be utilized
as a specialized filtering algorithm for certain non-binary
constraints. Real-world problems usually include a variety of
non-binary constraints. For some of these constraints we may have
efficient filtering algorithms in our disposal (e.g. the
all-different constraint), while for others no such algorithm may
exist. Also, some constraints may be extensionally specified by
the user. This is common, for example in configuration problems,
since many non-expert users find it difficult to model their
problems using advanced structures such as global constraints.
Extensionally specified constraints, or constraints with no known
efficient filtering algorithm, are usually handled using a generic
GAC algorithm. For example, ILOG Solver provides the *Table*
constraint which implements GAC-schema [Bessière RéginBessière Régin1996a]. Alternatively,
a weaker propagation algorithm (e.g. FC) is used. We provide a
third alternative since PW-AC can be used as a filtering algorithm
for these classes of constraints, assuming the DE of the
constraints is feasible with respect to the space it requires. The
PW-AC algorithm has a competitive asymptotic complexity with
generic optimal GAC algorithms and at the same time it achieves a
higher level of consistency. Therefore, we can model some
non-binary constraints in a problem using the DE while for others
we keep the non-binary representation, depending on the type of
the constraints. The practical benefits of such hybrid models are
demonstrated through experimental results in
Section 6.3

Nikolaos Samaras 2005-11-09