Linear programming relaxation: Difference between revisions

Revision as of 04:52, 11 January 2008

Revision as of 16:55, 24 March 2008

Line 1:

In mathematics, the '''LP-relaxation''' of a [[linear0-1 integer programming]] (LP) problem with|0-1 integer constraintsprogram]] is the problem that arises whenby replacing the integerconstraint constraintsthat areeach dropped.variable This canmust be used0 toor reduce1 mixedby integera programmingweaker (MIP) problemsconstraint, inthat whicheach somevariable variables are requiredbelong to take on a discrete set of values, orthe [[discreteInterval optimization(mathematics)|interval]] problems[0, in which all variables have to satisfy such a requirement, to LP-form1].

That is, for each constraint of the form

Once we drop the requirement, we are in a situation where we may solve

:<math>x_i\in\{0,1\}</math>

the problem, using one of the many known solvers for LP problems. We

of the original integer program, we instead use a pair of linear constraints

must however later check that the discrete requirements are fulfilled,

:<math>0 \le x_i \le 1.</math>

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

The resulting relaxation is a [[linear program]], hence the name.

==Using the LP-relaxation to solve the original integer program==

The LP-relaxation of an integer program may be solved using any standard linear programming technique. If the optimal solution to the linear program happens to have all variables either 0 or 1, it will also be an optimal solution to the original integer program. However, this is generally not true, except for some special cases (e.g.,

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

If thissome isvariables notin truethe optimal solution have fractional values, we may start a [[branch and bound]] type process, in which we recursively solve subproblems in which some of the fractional variables have their values fixed to either zero or one.

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

For any subproblem in this process, the LP relaxation provides a valid bound on the solution quality of the optimal integer solution. Therefore, if a subproblem's LP relaxation has a solution quality that is not better than the best integer solution found so far, that branch of the search may be pruned without further searching.

==References==