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

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 revise procedure ever proposed in 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
JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.23-31, 2010
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00520371
Contributeur : Christophe Lecoutre <>
Soumis le : jeudi 23 septembre 2010 - 09:16:48
Dernière modification le : jeudi 11 janvier 2018 - 16:39:48
Document(s) archivé(s) le : jeudi 25 octobre 2012 - 11:22:22

Fichier

araya.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : inria-00520371, version 1

Citation

Ignacio Araya, Bertrand Neveu, Gilles Trombettoni. Exploitation de la monotonie des fonctions dans la propagation de contraintes sur intervalles. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.23-31, 2010. 〈inria-00520371〉

Partager

Métriques

Consultations de la notice

291

Téléchargements de fichiers

192