Weakly Monotonic Propagators
2009 (English)In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING / [ed] Gent IP, 2009, Vol. 5732, 723-730 p.Conference paper (Refereed)
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 it 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 call be seen as all opportunity for more efficient propagation.
Place, publisher, year, edition, pages
2009. Vol. 5732, 723-730 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 5732
Constraint programming systems, Constraint propagation, Constraint solvers, Minimal properties, Monotonicity, Non-monotonicity, Realistic model, Computer programming
IdentifiersURN: urn:nbn:se:kth:diva-30347DOI: 10.1007/978-3-642-04244-7_56ISI: 000273241200053ScopusID: 2-s2.0-70350413800ISBN: 978-3-642-04243-0OAI: oai:DiVA.org:kth-30347DiVA: diva2:401707
15th International Conference on Principles and Practice of Constraint Programming (CP 2009), Lisbon, PORTUGAL, SEP 20-24, 2009
QC 201103032011-03-032011-02-242016-05-25Bibliographically approved