Publication details

Saarland University Computer Science

Weakly Monotonic Propagators

Christian Schulte, Guido Tack

Proceedings of the 15th international conference on principles and practice of constraint programming, Vol. 5732 of LNCS, pp. 723-730, Springer, 2009

Today's models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. These models do not comply with reality: today's constraint programming systems actually use non-monotonic propagators. This paper introduces the first realistic model of constraint propagation by assuming a propagator to be weakly monotonic (complying with the constraint it implements). Weak monotonicity is shown to be the minimal property that guarantees constraint propagation to be sound and complete. The important insight is that weak monotonicity makes propagation in combination with search well behaved. A case study suggests that non-monotonicity can be seen as an opportunity for more efficient propagation.

Springer-Verlag, (Lecture Notes in Computer Science)

Download PDF        Show BibTeX        Download slides (PDF)       


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009