Name
Abstract | ||
|---|---|---|
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.
|
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-04244-7_56 | Principles and Practice of Constraint Programming |
Keywords | Field | DocType |
efficient propagation,weakly monotonic propagator,constraint programming system,weak monotonicity,constraint propagation,nonmonotonic propagator,propagation-based constraint solvers,minimal property,case study,important insight,weakly monotonic,constraint programming,computer science | Constraint satisfaction,Monotonic function,Discrete mathematics,Mathematical optimization,Local consistency,Computer science,Constraint programming,Constraint satisfaction problem,Propagator,Constraint logic programming,Binary constraint | Conference |
Volume | ISSN | ISBN |
5732 | 0302-9743 | 3-642-04243-0 |
Citations | PageRank | References |
5 | 0.44 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Schulte | 1 | 387 | 33.89 |
| Guido Tack | 2 | 377 | 27.56 |