Dynamic optimization of interval narrowing algorithms

Olivier Lhomme 1 Arnaud Gotlieb 2 Michel Rueher 3
2 CELTIQUE - Software certification with semantic analysis
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
3 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe CEP
Laboratoire I3S - MDSC - Modèles Discrets pour les Systèmes Complexes
Abstract : Interval narrowing techniques are a key issue for handling constraints over real numbers in the logic programming framework. However, the standard fixpoint algorithm used for computing an approximation of arc consistency may give rise to cyclic phenomena and hence to problems of slow convergence. Analysis of these cyclic phenomena shows: 1) that a large number of operations carried out during a cycle are unnecessary; 2) that many others could be removed from cycles and performed only once when these cycles have been processed. What is proposed here is a revised interval narrowing algorithm for identifying and simplifying such cyclic phenomena dynamically. These techniques are of particular interest for computing stronger consistencies which are often required for a substantial pruning. Experimental results show that such dynamic optimizations improve performance significantly.
Document type :
Journal articles
Liste complète des métadonnées

https://hal.inria.fr/inria-00540302
Contributor : Arnaud Gotlieb <>
Submitted on : Friday, November 26, 2010 - 12:50:56 PM
Last modification on : Friday, November 16, 2018 - 1:40:54 AM
Document(s) archivé(s) le : Friday, October 26, 2012 - 4:55:54 PM

File

jlp97.pdf
Files produced by the author(s)

Identifiers

Citation

Olivier Lhomme, Arnaud Gotlieb, Michel Rueher. Dynamic optimization of interval narrowing algorithms. Journal of Logic Programming, Elsevier, 1998, 37 (1-3), pp.165-183. ⟨10.1016/S0743-1066(98)10007-9⟩. ⟨inria-00540302⟩

Share

Metrics

Record views

500

Files downloads

133