DYNAMIC OPTIMIZATION OF INTERVAL NARROWING ALGORITHMS

Interval narrowing techniques are a key issue for handling constraints over real numbers in the logic programming framework. However, the st andard fixpoint algorithm used for computing an approximation of are c onsistency 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 simplifyin g such cyclic phenomena dynamically. These techniques are of particula r interest for computing stronger consistencies which are often requir ed for a substantial pruning. Experimental results show that such dyna mic optimizations improve performance significantly. (C) 1998 Elsevier Science Inc. All rights reserved.