Box consistency through weak box consistency

Abstract

Interval constraint solvers use local consistencies-among which one worth mentioning is box consistency-for computing verified solutions of real constraint systems. Though among the most efficient ones, the algorithm for enforcing box consistency suffers from the use of time-consuming operators. This paper first introduces box/sub /spl phi// consistency, a weakening of box consistency; this new notion then allows us to devise an adaptive algorithm that computes box consistency by enforcing box/sub /spl phi// consistency, decreasing the /spl phi/ parameter as variables' domains get tightened, then achieving eventually box/sub 0/ consistency, which is equivalent to box consistency. A new propagation algorithm is also given, that intensifies the use of the most contracting pruning functions based on box/spl phi/ consistency. The resulting algorithm is finally shown to outperform the original scheme for enforcing box consistency on a set of standard benchmarks.