Theory and Practice of Logic Programming| Author(s) | Guy A. Narboni | | Country | France | | Affiliation | Implexe | | Title | Propagation Properties of Min-closed CSPs | | Keywords | Interval solvers, Bounds-propagation, Min-closed constraints | | Abstract | Min-closed constraints are numerical relationships characterised by a simple property. Yet, with
finite-domain variables, min-closed systems give rise to a polynomial class of Constraint Satisfaction
Problems. Propagation alone checks them for satisfiability. Solving is therefore search-free.
Can this result be generalized from a discrete to a continuous (or mixed) setting?
In this paper,
we investigate the use of interval solvers for handling constraints with real variables. We show
that the completeness result observed in the discrete case gracefully degrades into a 'close approximation'
property in the continuous case. When switching from finite to infinite domains,
the pruning power of propagation remains intact in the sense that it provides a box enclosure
whose lower bound cannot be further updated (even by domain splitting). Applications of this
analysis to scheduling, rule-based reasoning and scientific simulation are briefly mentioned. |
Technical communication
 30th International Conference on Logic Programming www
July 2014, Vienna, Austria. |
|
