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
Theory and Practice of Logic Programming, Volume 14 - Special Issue 4-5, 2014  30th International Conference on Logic Programming www
July 2014, Vienna, Austria.