Linear programming relaxation

As (derived from Linear Programming ) LP relaxation is called when there is a problem of integer linear optimization, the requirement of integrality is abandoned.

Thus, for example, replaces the constraints of the form

The original integer programming problem by the relaxed constraints

The problem ("Program" ) can be solved using linear optimization in the relaxed form. The resulting real solution met only in exceptional cases, the integrality constraints of the original problem, with their help, however, conclusions about the solution of the original problem can be drawn. The solution of the relaxed problem can also be used as an approximate solution for an integer programming algorithm.

This is of interest as an NP-hard ( integer ) is transferred into an optimization problem related ( real ) problem through the LP relaxation, which can be solved in polynomial time.

The method was described by Shmuel Agmon in 1954.

A relaxation in the context of an optimization problem (for example, maximization of an objective function ) is then generally speaking, when the amount of permissible solutions is increased. Result, the maximum target function value is not reduced.

Example

A detailed illustrative example and with sketch is specified in Article integer linear optimization.

531737
de