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.[5]
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.[1]
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.[1]
Some relaxation techniques
- Linear programming relaxation
- Lagrangian relaxation
- Semidefinite relaxation
- Surrogate relaxation and duality
Notes
- ↑ 1.0 1.1 1.2 Geoffrion (1971)
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.. MR 2571910)
- ↑ Relaxation methods for finding feasible solutions to linear inequality systems arise in linear programming and in Lagrangian relaxation. Goffin (1980) and Minoux (1986)|loc=Section 4.3.7, pp. 120–123 cite Shmuel Agmon (1954), and Theodore Motzkin and Isaac Schoenberg (1954), and L. T. Gubin, Boris T. Polyak, and E. V. Raik (1969).
References
- Lua error in package.lua at line 80: module 'strict' not found.
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found.
- Lua error in package.lua at line 80: module 'strict' not found.
- W. R. Pulleyblank, Polyhedral combinatorics (pp. 371–446);
- George L. Nemhauser and Laurence A. Wolsey, Integer programming (pp. 447–527);
- Claude Lemaréchal, Nondifferentiable optimization (pp. 529–572);
- Lua error in package.lua at line 80: module 'strict' not found.
- Lua error in package.lua at line 80: module 'strict' not found.