Tech Report CS-91-65

A Generic Arc Consistency Algorithm and Its Specializations

Pascal Van Hentenryck, Yves Deville and Choh-Man Teng

December 1991

Abstract:

Consistency techniques have been studied extensively in the past as a way of tackling constraint satisfaction problems (CSP). In particular, various arc-consistency algorithms have been proposed, originating from Waltz's filtering algorithm and culminating in the optimal algorithm AC-4 of Mohr and Henderson. AC-4 runs in $O(ed^2)$ in the worst case where $e$ is the number of arcs (or constraints) and $d$ is the size of the largest domain. Being applicable to the whole class of (binary) CSP, these algorithms do not take into account the semantics of constraints.

In this paper we present a new generic arc-consistency algorithm AC-5. The algorithm is parameterized on two specified procedures and can be instantiated to reduce to AC-3 and AC-4. More important, AC-5 can be instantiated to produce an $O(ed^2)$ algorithm for a number of important classes of constraints: functional, anti-functional, monotonic and their generalization to (functional, anti-functional, and monotonic) piecewise constraints.

We also show that AC-5 has an important application in constraint logic programming over finite domains. The kernel of the constraint-solver for such a programming language is an arc-consistency algorithm for a set of basic constraints. We prove that AC-5, in conjuction with node consistency, provides a decision procedure for these constraints running in time $O(ed)$.

(complete text in pdf)