Constraint Satisfaction Problems (CSPs) are composed of sets of constraints defining relations between variables to which are associated sets of possible values called domains. Consistency techniques aim at reducing as much as possible the domains by removing some values which do not satisfy the constraints. Among others, arc-consistency over finite domains is computed by some Waltz-like constraint propagation algorithm (we consider here AC3) which iterates contraction of one variable domain using a constraint and propagation of the new domain to all the constraints sharing this variable, until no more reduction occurs.
Recently, many authors (Hyvonen, Lhomme, Faltings, Benhamou) have extended this work to deal with continuous domains, in particular for solving so-called interval constraints. This work is based on the general framework proposed by Benhamou for heterogeneous constraint solving. Essentially, the variable domains are elements of approximate domains which are subsets of the powerset of IR, and the domain reductions are modeled by constraint narrowing operators which are closure operators over lattices of approximate domains. The propagation algorithm we use is an immediate adaptation of AC3 which is the most appropriate arc-consistency algorithm for continuous domains.
Intuitively, the resolution process of a CSP is decomposed in two phases: the association of well chosen constraint narrowing operators to constraints and then the application of AC3 to reduce the variable domains using the narrowing operators. In our experiments, one narrowing operator computing the well-known box-consistency over intervals for real constraints will be associated to each variable in each constraint.