Interval contractor

In mathematics, an interval contractor associated to a set is an operator which associates to a hyperrectangle in another box of such that the two following properties are always satisfied:
A contractor associated to a constraint is a
contractor associated to the set of all 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
It is minimal if for all boxes, we have
where 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,
where denotes the degenerated box enclosing x as a single point.
The contractor C is idempotent if for all boxes, we have
The contractor C is convergent if for all sequences of boxes containing x, we have

Illustration

Figure 1 represents the set X painted grey and some boxes, some of them degenerated. 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.

Contractor algebra

Some operations can be performed on contractors to build more complex contractors.
The intersection, the union, the composition and the repetition are defined as follows.

Building contractors

There exist different ways to build contractors associated to equations and inequalities, say, f in .
Most of them are based on interval arithmetic.
One of the most efficient and most simple is the forward/backward contractor.
The principle is to evaluate f using interval arithmetic.
The resulting interval is intersected with . A backward evaluation of f is then performed
in order to contract the intervals for the x_i. We now illustrate the principle on a simple example.
Consider the constraint
We can evaluate the function f by introducing the two intermediate
variables a and b, as follows
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
The resulting forward/backward contractor
is obtained by evaluating the forward and the backward constraints using interval analysis.