Exploitation de la monotonie des fonctions dans la propagation de contraintes sur intervalles

Translated title of the contribution: Exploitation of the monotony of functions in interval constraint propagation

IGNACIO DANIEL ARAYA ZAMORANO, Gilles Trombettoni, Bertrand Neveu

Research output: Contribution to conferencePaperpeer-review

1 Scopus citations

Abstract

We propose 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 re- vise procedure ever proposed in constraint program- ming. 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.

Translated title of the contributionExploitation of the monotony of functions in interval constraint propagation
Original languageFrench
Pages23-31
Number of pages9
StatePublished - 1 Dec 2010
EventSixiemes Journees Francophones de Programmation par Contraintes, JFPC 2010 - 6th French Speaking Conference on Constraint Programming, JFPC 2010 - Caen, France
Duration: 9 Jun 201011 Jun 2010

Conference

Conference
CountryFrance
CityCaen
Period9/06/1011/06/10

Cite this