Relaxation (approximation)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. 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. However, iterative methods of relaxation have been used to solve Lagrangian relaxations.

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. 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. However, iterative methods of relaxation have been used to solve Lagrangian relaxations. z = \min \{c(x) : x \in X \subseteq \mathbf{R}^{n}\} is another minimization problem of the form z_R = \min \{c_R(x) : x \in X_R \subseteq \mathbf{R}^{n}\} 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

If 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 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, Nondifferentiable optimization (pp. 529–572);

Text derived from https://en.wikipedia.org/w/index.php?oldid=1270244199 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001270244199 · captured 1737214776.0 · version history

Cite this page as: encyclopegia.org, “Relaxation (approximation)”, snapshot enwiki-001270244199. https://encyclopegia.org/a/relaxation-approximation

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.