In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, an interval contractor (or contractor for short) associated to a set
is an operator
which associates to a
hyperrectangle
In geometry, a hyperrectangle (also called a box, hyperbox, k-cell or orthotopeCoxeter, 1973), is the generalization of a rectangle (a plane figure) and the rectangular cuboid (a solid figure) to higher dimensions. A necessary and sufficient cond ...
equation
In mathematics, an equation is a mathematical formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for ...
or an
inequality
Inequality may refer to:
* Inequality (mathematics), a relation between two quantities when they are different.
* Economic inequality, difference in economic well-being between population groups
** Income inequality, an unequal distribution of i ...
) 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
Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution.
It is an algorithm ...
algorithms classically used in
interval analysis.
Properties of contractors
A contractor ''C'' is
monotonic
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of ord ...
if we have
\subset \Rightarrow C( \subset C( .
It is ''minimal'' if for all boxes
'x'' we have
C( = xcap 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(\) = \\cap X
where denotes the degenerated box enclosing ''x'' as a single point.
The contractor ''C'' is ''
idempotent
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
'' if for all boxes
'x'' we have
C \circ C( = C( .
The contractor ''C'' is ''
convergent'' if for all sequences
'x''''k'') of boxes containing ''x'', we have
k) \rightarrow x \implies C( k))\rightarrow \ \cap X.
Illustration
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
Contraction may refer to:
Linguistics
* Contraction (grammar), a shortened word
* Poetic contraction, omission of letters for poetic reasons
* Elision, omission of sounds
** Syncope (phonology), omission of sounds in a word
* Synalepha, merged ...
. 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
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...
, the
union, the
composition
Composition or Compositions may refer to:
Arts and literature
*Composition (dance), practice and teaching of choreography
* Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
and the repetition are defined as follows.
:
(C_1 \cap C_2)( = C_1( \cap C_2(
:
(C_1 \cup C_2) ( = \cup C_2( ">_1( \cup C_2( /math>
: (C_1 \circ C_2) ( = C_1( C_2( )
: C^\infty( = C \circ C \circ C \circ \cdots \circ C(
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).
[
]
The principle is to evaluate ''f''(''x'') using
interval arithmetic
Interval arithmetic (also known as interval mathematics; interval analysis or interval computation) is a mathematical technique used to mitigate rounding and measurement errors in mathematical computation by computing function bounds. Numeri ...
(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 ,2
We can evaluate the function ''f''(''x'') by introducing the two intermediate
variables
Variable may refer to:
Computer science
* Variable (computer science), a symbolic name associated with a value and whose associated value may be changed
Mathematics
* Variable (mathematics), a symbol that represents a quantity in a mathemat ...
''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
:
a = \frac
:
x_1 = a-x_2
:
x_2 = a-x_1
The resulting forward/backward contractor
C( _1 _2 _3
is obtained by evaluating the forward and the backward constraints using
interval analysis.
:
= _1 _2/math>
: = \cdot _3/math>
: = \cap ,2/math>
: _3= _3 \cap \ \frac
: = \cap \frac
: _1= _1 \cap \ \ _2/math>
: _2= _2 \cap \ \ _1/math>
References
{{Reflist, 2
Arithmetic
Computer arithmetic
Optimization algorithms and methods
Numerical analysis