Numerical Properties of Min-closed CSPs

ABSTRACT. Min-closed constraints are numerical relationships characterised by a simple algebraic 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 noteworthy result be generalized from a discrete to a continuous (or mixed) setting, with constraints involving real variables, using interval solvers? In this paper, we show that the completeness property observed in the discrete case gracefully degrades into a ’close approximation’ property in the continuous case, which is also more general. When switching from finite to infinite domains, we show that 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). In the corresponding integer case, this box, when not empty, has a least element. This witness point thus ensures satisfiability and restores decidability. Applications of this analysis to scheduling, rule-based reasoning and scientific simulation are finally briefly mentionned.