An optimization relaxation is a problem obtained by enlarging the feasible set of an optimization problem while retaining its objective function.
Its optimum is a lower bound for a minimization problem
and an upper bound for a maximization problem. For
example, replacing a constraint 
by 
permits fractional values of 
. Relaxing the integrality constraints of integer
programming gives linear programming. Semidefinite programming supplies other
relaxations for discrete optimization. The integrality
gap measures the worst separation between the original and relaxed optima (Williamson
and Shmoys 2011, Definition 5.13).
Optimization Relaxation
See also
Integer Programming, Integrality Gap, Linear Programming, Optimization Theory, Semidefinite ProgrammingExplore with Wolfram|Alpha
References
Williamson, D. P. and Shmoys, D. B. The Design of Approximation Algorithms. New York: Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511921735.Cite this as:
Weisstein, Eric W. "Optimization Relaxation." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/OptimizationRelaxation.html