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ϕ consistency, a weakening of box consistency; this new notion then allows us to device an adaptative algorithm that computes box consistency by enforcing boxϕ consistency, decreasing the ϕ parameter as variables’ domains get tightened, then achieving eventually box0 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ϕ consistency. The resulting algorithm is finally shown to outperform the original scheme for enforcing box consistency on a set of standard benchmarks