Weakly Monotonic Propagators
Christian Schulte, Guido Tack.
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.
In: Ian Gent, editor, Fifteenth International Conference on Principles and Practice of Constraint Programming, Lisbon, Portugal, volume 5732 of Lecture Notes in Computer Science, pages 723-730. Springer-Verlag, September, 2009. DOI 10.1007/978-3-642-04244-7_56.
Copyright Springer-Verlag, the original publication is available at www.springerlink.com