# Relaxation

$LaTeX: P'$ is a relaxation of $LaTeX: P$ if: (1) the feasible region of $LaTeX: P'$ contains the feasible region of $LaTeX: P,$ and (2) the objective value in $LaTeX: P',$ say $LaTeX: F(x),$ is no worse than that of $LaTeX: P,$ say $LaTeX: f(x),$ for all $LaTeX: x$ in the domain of $LaTeX: P$ (for maximization, this means $LaTeX: \textstyle F(x) \ge f(x)$ for all $LaTeX: \textstyle x \in X$ ).

Some of the most common are as follows:
1. dropping integer restrictions (viz., we refer to the LP relaxation of a (linear) MIP);
2. dropping some constraints (viz., an active set method).
3. aggregating constraints (viz., using surrogate constraint);
4. using duality (viz., GLM).

One relaxation is sharper than another if its objective value is never further from the original. One way this can occur is for the objectives to be the same and the feasibility region to be less. In particular, one LP relaxation of a MIP is sharper than another if its feasible region is contained in the other.