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 equality (mathematics), equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very ...

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 function#As a polynomial function, li ...

relaxation of an integer programming problem removes the integrality constraint and so allows non-integer rational solutions. A

Lagrangian relaxation In the field of mathematical optimization, Lagrangian relaxation is a relaxation method which approximates a difficult problem of constrained optimization by a simpler problem. A solution to the relaxed problem is an approximate solution to the o ...

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 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 methods of relaxation, such as successive over-relaxation (SOR); iterative methods of relaxation are used in solving problems in differential equations, linear least-squares, and

. However, iterative methods of relaxation have been used to solve Lagrangian relaxations.

Definition

A ''relaxation'' of the minimization problem :

z = \min \

is another minimization problem of the form :

z_R = \min \

with these two properties #

X_R \supseteq X

c_R(x) \leq c(x)

for all

x \in X

. 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

x^*

is an optimal solution of the original problem, then

x^* \in X \subseteq X_R

and

z = c(x^*) \geq c_R(x^*)\geq z_R

. Therefore,

x^* \in X_R

provides an upper bound on

z_R

. If in addition to the previous assumptions,

c_R(x)=c(x)

\forall x\in X

, 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 ...

* Semidefinite relaxation *

Surrogate relaxation A surrogate is a substitute or deputy for another person in a specific role and may refer to: Relationships * Surrogacy, an arrangement where a woman agrees to carry and give birth to a child for another person who will become its parent at bir ...

and

duality Duality may refer to: Mathematics * Duality (mathematics), a mathematical concept ** Dual (category theory), a formalization of mathematical duality ** Duality (optimization) ** Duality (order theory), a concept regarding binary relations ** Dual ...

Notes

References

* * * * Translated by Steven Vajda from * * **

W. R. Pulleyblank William R. Pulleyblank is a Canadian and American operations researcher. He is a professor of operations research at the United States Military Academy (West Point), where he also holds the Class of 1950 Chair of Advanced Technology.Claude Lemaréchal, Nondifferentiable optimization (pp. 529–572); * * {{DEFAULTSORT:Relaxation (Approximation) Mathematical optimization Approximations