LP relaxation

As a linear programming relaxation (derived from linear programming ) when in a problem referred to, integer linear programming , the demand of the integrality is abandoned.

To replace z. B. Constraints of the shape

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

of the original integer optimization problem through the relaxed constraints

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

The problem (“program”) can be solved in the relaxed form with the help of linear optimization . The resulting real solution only fulfills the integer conditions of the original problem in exceptional cases, but with its help it is possible to draw conclusions about the solution of the original problem. The solution to the relaxed problem can also be used as an approximate solution for an algorithm for integer optimization.

This is of interest because LP relaxation transfers an NP-heavy (integer) optimization problem into a related (real) problem that can be solved in polynomial time .

The method was described by Shmuel Agmon in 1954.

From a relaxation in the context of an optimization problem (eg. As maximizing an objective function) is commonly spoken then, when the amount of allowable solutions is increased. This does not reduce the maximum objective function value.

example

A detailed and illustrative example with sketch is given in the article Integer Linear Optimization .

literature

• Shmuel Agmon: The relaxation method for linear inequalities . In: Canadian Journal of Mathematics . tape 6 , 1954, pp. 382-392 , doi : 10.4153 / CJM-1954-037-2 .