In mathematical optimization, relaxation is a modeling strategy that approximates a difficult problem by an easier one, providing useful insights into the original problem. For instance, a linear programming relaxation of an integer programming problem removes integrality constraints to allow rational solutions. Another approach, Lagrangian relaxation, simplifies combinatorial optimization by penalizing constraint violations. These techniques are often used alongside branch and bound algorithms to establish bounds for integer programming. It is important to distinguish this strategy from iterative relaxation methods like successive over-relaxation, which solve equations in fields such as differential equations and linear least-squares.
Definition
A relaxation of the minimization problem
z = min { c ( x ) : x ∈ X ⊆ R n } {\displaystyle 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 ∈ X R ⊆ R n } {\displaystyle z_{R}=\min\{c_{R}(x):x\in X_{R}\subseteq \mathbf {R} ^{n}\}}with these two properties
- X R ⊇ X {\displaystyle X_{R}\supseteq X}
- c R ( x ) ≤ c ( x ) {\displaystyle c_{R}(x)\leq c(x)} for all x ∈ X {\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.6
Properties
If x ∗ {\displaystyle x^{*}} is an optimal solution of the original problem, then x ∗ ∈ X ⊆ X R {\displaystyle x^{*}\in X\subseteq X_{R}} and z = c ( x ∗ ) ≥ c R ( x ∗ ) ≥ z R {\displaystyle z=c(x^{*})\geq c_{R}(x^{*})\geq z_{R}} . Therefore, x ∗ ∈ X R {\displaystyle x^{*}\in X_{R}} provides an upper bound on z R {\displaystyle z_{R}} .
If in addition to the previous assumptions, c R ( x ) = c ( x ) {\displaystyle c_{R}(x)=c(x)} , ∀ x ∈ 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.7
Some relaxation techniques
- Linear programming relaxation
- Lagrangian relaxation
- Semidefinite relaxation
- Surrogate relaxation and duality
Notes
- Buttazzo, G. (1989). Semicontinuity, Relaxation and Integral Representation in the Calculus of Variations. Pitman Res. Notes in Math. 207. Harlow: Longmann.
- Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848.
- Goffin, J.-L. (1980). "The relaxation method for solving systems of linear inequalities". Mathematics of Operations Research. 5 (3): 388–414. doi:10.1287/moor.5.3.388. JSTOR 3689446. MR 0594854.
- Minoux, M. (1986). Mathematical programming: Theory and algorithms. Chichester: A Wiley-Interscience Publication. John Wiley & Sons. ISBN 978-0-471-90170-9. MR 0868279. Translated by Steven Vajda from Programmation mathématique: Théorie et algorithmes. Paris: Dunod. 1983. MR 2571910.
- Murty, Katta G. (1983). "16 Iterative methods for linear inequalities and linear programs (especially 16.2 Relaxation methods, and 16.4 Sparsity-preserving iterative SOR algorithms for linear programming)". Linear programming. New York: John Wiley & Sons. ISBN 978-0-471-09725-9. MR 0720547.
- Nemhauser, G. L.; Rinnooy Kan, A. H. G.; Todd, M. J., eds. (1989). Optimization. Handbooks in Operations Research and Management Science. Vol. 1. Amsterdam: North-Holland Publishing Co. ISBN 978-0-444-87284-5. MR 1105099.
- 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);
- Rardin, Ronald L. (1998). Optimization in operations research. Prentice Hall. ISBN 978-0-02-398415-0.
- Roubíček, T. (1997). Relaxation in Optimization Theory and Variational Calculus. Berlin: Walter de Gruyter. ISBN 978-3-11-014542-7.
References
Geoffrion (1971) - Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848. https://doi.org/10.1137%2F1013001 ↩
Goffin (1980). - Goffin, J.-L. (1980). "The relaxation method for solving systems of linear inequalities". Mathematics of Operations Research. 5 (3): 388–414. doi:10.1287/moor.5.3.388. JSTOR 3689446. MR 0594854. https://doi.org/10.1287%2Fmoor.5.3.388 ↩
Murty (1983), pp. 453–464. - Murty, Katta G. (1983). "16 Iterative methods for linear inequalities and linear programs (especially 16.2 Relaxation methods, and 16.4 Sparsity-preserving iterative SOR algorithms for linear programming)". Linear programming. New York: John Wiley & Sons. ISBN 978-0-471-09725-9. MR 0720547. https://mathscinet.ams.org/mathscinet-getitem?mr=0720547 ↩
Minoux (1986). - Minoux, M. (1986). Mathematical programming: Theory and algorithms. Chichester: A Wiley-Interscience Publication. John Wiley & Sons. ISBN 978-0-471-90170-9. MR 0868279. https://mathscinet.ams.org/mathscinet-getitem?mr=0868279 ↩
Relaxation methods for finding feasible solutions to linear inequality systems arise in linear programming and in Lagrangian relaxation. [2][5][6][7][8] ↩
Geoffrion (1971) - Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848. https://doi.org/10.1137%2F1013001 ↩
Geoffrion (1971) - Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848. https://doi.org/10.1137%2F1013001 ↩