Relaxation (approximation)

In mathematical optimization and related fields, relaxation is a modeling strategy. A relaxation is an approximation 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 relaxation of an integer programming 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 algorithms of combinatorial optimization; linear programming and Lagrangian relaxations are used to obtain bounds in branch-and-bound algorithms for integer programming.^[1]

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 linear programming.^[2][3][4] However, iterative methods of relaxation have been used to solve Lagrangian relaxations.^[a]

Definition

A relaxation of the minimization problem

${\displaystyle z=\min\{c(x):x\in X\subseteq \mathbf {R} ^{n}\}}$

is another minimization problem of the form

${\displaystyle z_{R}=\min\{c_{R}(x):x\in X_{R}\subseteq \mathbf {R} ^{n}\}}$

with these two properties

1. ${\displaystyle X_{R}\supseteq X}$
2. ${\displaystyle c_{R}(x)\leq c(x)}$ for all ${\displaystyle 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.^[1]

Properties

If ${\displaystyle x^{*}}$ is an optimal solution of the original problem, then ${\displaystyle x^{*}\in X\subseteq X_{R}}$ and ${\displaystyle z=c(x^{*})\geq c_{R}(x^{*})\geq z_{R}}$. Therefore, ${\displaystyle x^{*}\in X_{R}}$ provides an upper bound on ${\displaystyle z_{R}}$.

If in addition to the previous assumptions, ${\displaystyle c_{R}(x)=c(x)}$, ${\displaystyle \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.^[1]

Some relaxation techniques

• Linear programming relaxation
• Lagrangian relaxation
• Semidefinite relaxation
• Surrogate relaxation and duality