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.
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.
[a] A relaxation of the minimization problem is another minimization problem of the form with these two properties 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.
is an optimal solution of the original problem, then
, 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.