Discussion

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