# Relaxation

### From Glossary

is a relaxation of if: (1) the feasible region of contains the feasible region of and (2) the objective value in say is no worse than that of say for all in the domain of (for maximization, this means for all ).

- Some of the most common are as follows:

- dropping integer restrictions (viz., we refer to the
*LP relaxation*of a (linear) MIP); - dropping some constraints (viz., an active set method).
- aggregating constraints (viz., using surrogate constraint);
- 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.