LP relaxation

From Wikipedia, the free encyclopedia

In mathematics, the LP-relaxation of a linear programming (LP) problem with integer constraints is the problem that arises when the integer constraints are dropped. This can be used to reduce mixed integer programming (MIP) problems, in which some variables are required to take on a discrete set of values, or discrete optimization problems, in which all variables have to satisfy such a requirement, to LP-form.

Once we drop the requirement, we are in a situation where we may solve the problem, using one of the many known solvers for LP problems. We must however later check that the discrete requirements are fulfilled, which is generally not true, except for some special cases (e.g., problems with totally unimodular matrix specifications.)

If this is not true, we may start a branch and bound type process, where we fixate a single non set variable to a variable within the set.