Relaxation

From Glossary

Jump to: navigation, search

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.


Views
Personal tools