Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Exploiting Monotonicity in Interval Constraint Propagation

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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal-enpc.archives-ouvertes.fr/hal-00654400
Contributeur : Gilles Trombettoni <>
Soumis le : mercredi 21 décembre 2011 - 18:12:27
Dernière modification le : mercredi 26 février 2020 - 19:06:06

Identifiants

  • HAL Id : hal-00654400, version 1

Citation

Ignacio Araya, Gilles Trombettoni, Bertrand Neveu. Exploiting Monotonicity in Interval Constraint Propagation. Twenty-Fourth AAAI Conference on Artificial Intelligence, Jul 2010, Atlanta, United States. pp.9-14. ⟨hal-00654400⟩

Partager

Métriques

Consultations de la notice

367