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
Complete list of metadatas

Contributor : Arnaud Gotlieb <>
Submitted on : Friday, November 26, 2010 - 12:50:56 PM
Last modification on : Friday, November 16, 2018 - 1:40:54 AM
Long-term archiving on: Friday, October 26, 2012 - 4:55:54 PM


Files produced by the author(s)



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⟩



Record views


Files downloads