In
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
and related fields, relaxation is a
modeling strategy. A relaxation is an
approximation
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix '' ...
of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about the original problem.
For example, a
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
relaxation of an
integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...
problem removes the integrality constraint and so allows non-integer rational solutions. A
Lagrangian relaxation of a complicated problem in combinatorial optimization penalizes violations of some constraints, allowing an easier relaxed problem to be solved. Relaxation techniques complement or supplement
branch and bound
Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutio ...
algorithms of combinatorial optimization; linear programming and Lagrangian relaxations are used to obtain bounds in branch-and-bound algorithms for integer programming.
The modeling strategy of relaxation should not be confused with
iterative method
In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived from the pre ...
s of
relaxation, such as
successive over-relaxation In numerical linear algebra, the method of successive over-relaxation (SOR) is a variant of the Gauss–Seidel method for solving a linear system of equations, resulting in faster convergence. A similar method can be used for any slowly converging ...
(SOR); iterative methods of relaxation are used in solving problems in
differential equation
In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, an ...
s,
linear least-squares, and
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
. However, iterative methods of relaxation have been used to solve Lagrangian relaxations.
Definition
A ''relaxation'' of the minimization problem
:
is another minimization problem of the form
:
with these two properties
#
#
for all
.
The first property states that the original problem's feasible domain is a subset of the relaxed problem's feasible domain. The second property states that the original problem's objective-function is greater than or equal to the relaxed problem's objective-function.
Properties
If
is an optimal solution of the original problem, then
and
. Therefore,
provides an upper bound on
.
If in addition to the previous assumptions,
,
, the following holds: If an optimal solution for the relaxed problem is feasible for the original problem, then it is optimal for the original problem.
Some relaxation techniques
*
Linear programming relaxation
In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.
For example, in a 0–1 integer program, all constraints are of the form
:x_i\in\.
The relax ...
*
Lagrangian relaxation
*
Semidefinite relaxation
*
Surrogate relaxation and
duality
Notes
References
*
*
*
* Translated by Steven Vajda from
*
*
**
W. R. Pulleyblank, Polyhedral combinatorics (pp. 371–446);
** George L. Nemhauser and Laurence A. Wolsey, Integer programming (pp. 447–527);
**
Claude Lemaréchal
Claude Lemaréchal is a French applied mathematician, and former senior researcher (''directeur de recherche'') at INRIA near Grenoble, France.
In mathematical optimization, Claude Lemaréchal is known for his work in numerical methods for nonl ...
, Nondifferentiable optimization (pp. 529–572);
*
*
{{DEFAULTSORT:Relaxation (Approximation)
Mathematical optimization
Approximations