Exploiting Monotonicity in Interval Constraint Propagation

Authors

  • Ignacio Araya INRIA
  • Gilles Trombettoni INRIA, University of Nice-Sophia
  • Bertrand Neveu Imagine LIGM university Paris-Est

DOI:

https://doi.org/10.1609/aaai.v24i1.7541

Keywords:

constraint propagation, intervals, monotonicity

Abstract

We propose in this paper a new interval constraint propagation algorithm, called MOnotonic Hull Consistency (Mohc), that exploits monotonicity of functions. The propagation is standard, but the Mohc-Revise procedure, used to filter/contract the variable domains w.r.t. an individual constraint, uses monotonic versions of the classical HC4-Revise and BoxNarrow procedures. Mohc-Revise appears to be the first adaptive revise procedure ever proposed in (interval) constraint programming.  Also, when a function is monotonic w.r.t. every variable, Mohc-Revise is proven to compute the optimal/sharpest box enclosing all the solutions of the corresponding constraint (hull consistency). Very promising experimental results suggest that Mohc has the potential to become an alternative to the state-of-the-art HC4 and Box algorithms.

Downloads

Published

2010-07-03

How to Cite

Araya, I., Trombettoni, G., & Neveu, B. (2010). Exploiting Monotonicity in Interval Constraint Propagation. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 9-14. https://doi.org/10.1609/aaai.v24i1.7541

Issue

Section

Constraints, Satisfiability, and Search