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
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.
Type de document :
Article dans une revue
Journal of Logic Programming, Elsevier, 1998, 37 (1-3), pp.165-183. <10.1016/S0743-1066(98)10007-9>
Liste complète des métadonnées

https://hal.inria.fr/inria-00540302
Contributeur : Arnaud Gotlieb <>
Soumis le : vendredi 26 novembre 2010 - 12:50:56
Dernière modification le : jeudi 9 février 2017 - 16:03:45
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 16:55:54

Fichier

jlp97.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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>

Partager

Métriques

Consultations de
la notice

255

Téléchargements du document

87