Dynamic optimization of interval narrowing algorithms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Logic Programming Année : 1998

Dynamic optimization of interval narrowing algorithms

Résumé

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.
Fichier principal
Vignette du fichier
jlp97.pdf (603.09 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00540302 , version 1 (26-11-2010)

Identifiants

Citer

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⟩
187 Consultations
96 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More