L'arithmétique des intervalles

Nous allons dans cette section, donner les définitions de bases de l'arithmétique des intervalles [17], nécessaire à la compréhension des techniques de filtrage locale dans les domaines continus. Un intervalle $[a,b]$ avec $a \leq b$ est l''ensemble des valeurs réelles comprises entre $a$ et $b$. L'arithmétique des intervalles est une extension de l'arithmétique sur les réels et définit les opérations $\times$, $+$, $-$, et $/$ de la manière suivante :

• $[a,b] + [c,d] = [a+c,\: b+d]$
• $[a,b] - [c,d] = [a-d,\: b-c]$
• $[a,b] \times [c,d] = [$min $(ac, ad, bc, bd)$, max $(ac, ad, bc, bd)]$
• $[a,b] \:\: / \:\: [c,d] = [$min $(\frac{a}{c},\frac{a}{d}, \frac{b}{c}, \frac{b}{d})$, max $(\frac{a}{c}, \frac{a}{d}, \frac{b}{c}, \frac{b}{d})]$

La commutativité et l'associativité est respectée pour l'addition et la multiplication mais pas la distributivité dans le cas général. On peut étendre cet arithmétique de base aux fonctions mathématiques de base(exponentielle, logarithme, puissance $\ldots$), mais le résultat de l'application d'une fonction à un intervalle n'est pas toujours un intervalle. C'est le cas lorsque la fonction est continue et monotone sur l'intervalle. Lorsque la fonction n'est pas monotone sur un intervalle, il faut le décomposer en domaines sur lesquels la fonction est monotone. La règle de base de l'arithmétique des intervalles est que si $x \in [a,b]$ alors $f(x) \in F([a,b]$, avec $F$ extension de $f$ aux intervalles.
Fonction de projection :
Les techniques de consistance locale utilisent une fonction de projection d'une contrainte pour mettre à jour le domaine d'une variable. Pour une contrainte $c$ mettant en jeu les variables $(X_1, \ldots, X_k)$, il s'agit d'exprimer la variable $X_j$ en une fonction $F_j$ des autres variables. La valeur de retour est l'intersection entre le domaine de $X_j$ et l'application de $F_j$ aux domaines des autres variables.