Boosting the Interval Narrowing Algorithm.

Abstract

Interval narrowing techniques are a key issue for handling constraints over real numbers in the logic programming framework. However, the standard fixed-point algorithm used for interval narrowing 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. First experimental results show that this approach improves performance significantly.