Skip to Main content Skip to Navigation
New interface
Journal articles

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 metadata
Contributor : Arnaud Gotlieb Connect in order to contact the contributor
Submitted on : Friday, November 26, 2010 - 12:50:56 PM
Last modification on : Friday, August 5, 2022 - 3:31:09 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, 1998, 37 (1-3), pp.165-183. ⟨10.1016/S0743-1066(98)10007-9⟩. ⟨inria-00540302⟩



Record views


Files downloads