October 12-16, 1999
Alexandria, Virginia, USA

xywang@gmu.edu

The Rough Guide to Constraint Propagation

Krzysztof R. Apt
CWI and University of Amsterdam
The Netherlands

Constraint propagation algorithms (also known as (local) consistency, consistency enforcing, (Waltz) filtering or narrowing algorithms) lie at the heart of constraint programming. We show that most of these algorithms, including well-known (directional) arc consistency and (directional) path consistency algorithms AC-3, PC-2, DAC and DPC , are instances of a single generic algorithm.

In the proposed framework we proceed in two steps. First, we introduce a generic iteration algorithm on partial orderings and prove its correctness in an abstract setting. Then we instantiate this algorithm with specific partial orderings and functions. The partial orderings will be related to the considered variable domains and the assumed constraints, while the functions will be the ones that characterize considered notions of local consistency in terms of fixpoints.

The proposed framework builds upon the work of others by using in addition to the already considered notions of monotonicity, idempotence and inflationarity (alias contractance), the notions of commutativity and semi-commutativity. This approach allows us to easier verify, compare, modify, parallelize or combine the constraint propagation algorithms.