Exploiting monotonicity in interval constraint propagation

Ignacio Araya, Gilles Trombettoni, Bertrand Neveu

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

29 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Título de la publicación alojadaAAAI-10 / IAAI-10 - Proceedings of the 24th AAAI Conference on Artificial Intelligence and the 22nd Innovative Applications of Artificial Intelligence Conference
EditorialAI Access Foundation
Páginas9-14
Número de páginas6
ISBN (versión impresa)9781577354642
EstadoPublicada - 2010
Publicado de forma externa
Evento24th AAAI Conference on Artificial Intelligence and the 22nd Innovative Applications of Artificial Intelligence Conference, AAAI-10 / IAAI-10 - Atlanta, GA, Estados Unidos
Duración: 11 jul. 201015 jul. 2010

Serie de la publicación

NombreProceedings of the National Conference on Artificial Intelligence
Volumen1

Conferencia

Conferencia24th AAAI Conference on Artificial Intelligence and the 22nd Innovative Applications of Artificial Intelligence Conference, AAAI-10 / IAAI-10
País/TerritorioEstados Unidos
CiudadAtlanta, GA
Período11/07/1015/07/10

Citar esto