Linear programming relaxation

In mathematics, the LP-relaxation of a 0-1 integer program is the problem that arises by replacing the constraint that each variable must be 0 or 1 by a weaker constraint, that each variable belong to the interval [0,1].

That is, for each constraint of the form

${\displaystyle x_{i}\in \{0,1\}}$

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

${\displaystyle 0\leq x_{i}\leq 1.}$

The resulting relaxation is a linear program, hence the name. This relaxation technique transforms an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming); the solution to the relaxed linear program can be used to gain information about the solution to the original integer program.

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 some variables in the 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.

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

• Agmon, Shmuel (1954). "The relaxation method for linear inequalities". Canadian Journal of Mathematics. 6: 382–392.
• Motzkin, TS (1954). "The relaxation method for linear inequalities". Canadian Journal of Mathematics. 6: 393–404. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)