Interval contractor

In mathematics, an interval contractor (or contractor for short) ^[1] associated to a set X is an operator C which associates to a box [x] in Rⁿ another box C([x]) of Rⁿ such that the two following properties are always satisfied

$C([x])\subset [x]$ (contractance property)

$C([x])\cap X=[x]\cap X$ (completeness property)

A contractor associated to a constraint (such as an equation or an inequality) is a contractor associated to the set X of all x which satisfy the constraint. Contractors make it possible to improve the efficiency of branch-and-bound algorithms classically used in interval analysis.

Properties of contractors

A contractor C is monotonic if we have $[x] \subset [y] \Rightarrow C([x])\subset C([y])$

It is minimal if for all boxes [x], we have $C([x])=[[x]\cap X]$ , where [A] is the interval hull of the set A, i.e., the smallest box enclosing A.

The contractor C is thin if for all points x, $C(\{x\})=\{x\}\cap X$ where {x} denotes the degenerated box enclosing x as a single point.

The contractor C is idempotent if for all boxes [x], we have $C \circ C([x]) = C([x]).$

The contractor C is convergent if for all sequences [x](k) of boxes containing x, we have $[x](k)\rightarrow x \Rightarrow C([x](k))\rightarrow \{x\}\cap X.$

Illustration

Figure 1 represents the set X painted grey and some boxes. Some of them of 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 contractor is minimal for the cyan box but is pessimistic for the green one. All degenerated blue boxes are contracted to the empty box. The magenta box and the red box cannot be contracted.

Figure 1: Boxes before contraction

Figure 2: Boxes after contraction

Contractor algebra

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.

( C_1 \cap C_2)( [x]) =C_1 ( [x]) \cap C_2 ( [x])

( C_1 \cup C_2 ) ( [x]) = [ C_1 ([x]) \cup C_2 ( [x]) ]

( C_1 \circ C_2) ( [x]) =C_1 ( C_2 ([x]) )

C^\infty ( [x])=C\circ C\circ C\circ \cdots \circ C ([x])

Building contractors

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 x_i (this is the backward step). We now illustrate the principle on a simple example.

Consider the constraint $(x_1+x_2)\cdot x_3 \in [1,2].$ We can evaluate the function f(x) by introducing the two intermediate variables a and b, as follows

a =x_1+x_2

b =a\cdot x_3

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

x_3 =\frac{b}{a}

a =\frac{b}{x_3}

x_1=a-x_2

x_2=a-x_1

The resulting forward/backward contractor $C([x_1],[x_2],[x_3])$ is obtained by evaluating the forward and the backward constraints using interval analysis.

[a] =[x_1]+[x_2]

[b] =[a]\cdot [x_3]

[b] =[b]\cap [1,2]

[x_3] =[x_3]\ \cap \ \frac{[b]}{[a]}

[a] =[a]\cap \frac{[b]}{[x_3]}

[x_1] =[x_1]\ \cap \ \ [a]-[x_2]

[x_2] =[x_2]\ \cap \ \ [a]-[x_1]

References

↑ Jaulin, Luc; Kieffer, Michel; Didrit, Olivier; Walter, Eric (2001). Applied Interval Analysis. Berlin: Springer. ISBN 1-85233-219-0.
↑ Chabert, G.; Jaulin, L. (2009). "Contractor programming". Artificial Intelligence 173.
↑ Messine, F. (1997). Méthode d’optimisation globale basée sur l’analyse d’intervalles pour la résolution de problèmes avec contraintes. Thèse de doctorat, Institut National Polytechnique de Toulouse.
↑ Benhamou, F.; Goualard, F.; Granvilliers, L.; Puget, J.F. (1999). Revising hull and box consistency. In Proceedings of the 1999 international conference on Logic programming.