In mathematics, an interval contractor (or contractor for short)[1] associated to a set
X
C
[x]
\bold{R}n
C([x])
\bold{R}n
C([x])\subset[x]
C([x])\capX=[x]\capX
A contractor associated to a constraint (such as an equation or an inequality) is a contractor associated to the set
X
x
A contractor C is monotonic if we have
[x]\subset[y] ⇒ C([x])\subsetC([y])
It is minimal if for all boxes [''x''], we have
C([x])=[[x]\capX]
The contractor C is thin if for all points x,
C(\{x\})=\{x\}\capX
The contractor C is idempotent if for all boxes [''x''], we have
C\circC([x])=C([x]).
The contractor C is convergent if for all sequences [''x''](k) of boxes containing x, we have
[x](k) → x\impliesC([x](k)) → \{x\}\capX.
Figure 1 represents the set X painted grey and some boxes, some of them degenerated (i.e., they correspond to singletons). Figure 2 represents these boxes after contraction. Note that no point of X has been removed by the contractor. The contractoris minimal for the cyan box but is pessimistic for the green one. All degenerated blue boxes are contracted tothe empty box. The magenta box and the red box cannot be contracted.
Some operations can be performed on contractors to build more complex contractors.[2] The intersection, the union, the composition and the repetition are defined as follows.
(C1\capC2)([x])=C1([x])\capC2([x])
(C1\cupC2)([x])=[C1([x])\cupC2([x])]
(C1\circC2)([x])=C1(C2([x]))
Cinfty([x])=C\circC\circC\circ … \circC([x])
There exist different ways to build contractors associated to equations and inequalities, say, f(x) in [''y''].Most of them are based on interval arithmetic.One of the most efficient and most simple is the forward/backward contractor (also called as HC4-revise).[3] [4]
The principle is to evaluate f(x) using interval arithmetic (this is the forward step).The resulting interval is intersected with [''y'']. A backward evaluation of f(x) is then performed in order to contract the intervals for the xi (this is the backward step). We now illustrate the principle on a simple example.
Consider the constraint
(x1+x2) ⋅ x3\in[1,2].
a=x1+x2
b=a ⋅ x3
The two previous constraints are called forward constraints. We get the backward constraints by taking each forward constraint in the reverse order and isolating each variable on the right hand side. We get
x3=
| b | |
| a |
a=
| b | |
| x3 |
x1=a-x2
x2=a-x1
The resulting forward/backward contractor
C([x1],[x2],[x3])
[a]=[x1]+[x2]
[b]=[a] ⋅ [x3]
[b]=[b]\cap[1,2]
[x3]=[x3] \cap
| [b] | |
| [a] |
[a]=[a]\cap
| [b] | |
| [x3] |
[x1]=[x1] \cap [a]-[x2]
[x2]=[x2] \cap [a]-[x1]