Linear programming relaxation: Difference between revisions

Revision as of 12:10, 10 August 2006

Revision as of 10:04, 12 August 2006

Line 1:

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.

Given a problem on [[LP]] form, except the extra requirement that some variables (a [[MIP]] problem) or all variables (a [[DOP]] problem) are required to take on a discrete set of values.

The '''LP-relaxation''' of a [[MIP]] or a [[DOP]] is what we get if we drop these requirements.

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 problem]]sproblems. We

must however later check that the discrete requirements are fulfilled,

which is generally not true, except for some special cases. (Ege.g.,

problems with [[totally unimodular]] matrix specifications.)

If this is not true, we may start a [[Branchbranch and bound]] type process,

where we fixate a single non set variable to a variable within the set.