OR-Notes

J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

LP relaxation

For any IP we can generate an LP (called the LP relaxation) from the IP by taking the same objective function and same constraints but with the requirement that variables are integer replaced by appropriate continuous constraints

e.g. x_i = 0 or 1 can be replaced by the two continuous constraints x_i >= 0 and x_i <= 1

We can then solve this LP relaxation of the original IP.

For example consider the IP for the capital budgeting problem considered before.

The LP relaxation of this IP is given by:

maximise 0.2x₁ + 0.3x₂ + 0.5x₃ + 0.1x₄

subject to

0.5x₁ + 1.0x₂ + 1.5x₃ + 0.1x₄ <= 3.1

0.3x₁ + 0.8x₂ + 1.5x₃ + 0.4x₄ <= 2.5

0.2x₁ + 0.2x₂ + 0.3x₃ + 0.1x₄ <= 0.4

x_j <= 1 j=1,...,4

x_j >= 0 j=1,...,4

If we solve this LP then:

• the LP solution might turn out to have all variables taking integer values at the LP optimal solution - if so we have found the optimal integer solution (in such a case we have been lucky and the LP is said to be "naturally integer").

However for the LP relaxation of the capital budgeting problem the LP solution is x₁=0, x₂=0.5, x₃=1, x₄=0, so we have been unlucky.

If we have variables taking fractional values at the LP optimal solution then we can round these to the nearest integer value. If we do this then:

• this may lead to certain constraints being violated (i.e. we have an infeasible solution) - this may, or may not, be important.

For example if we round the LP solution given above to x₁=0, x₂=1, x₃=1, x₄=0 then the constraints relating to the amount of available capital in year 3 is violated.

• the solution may be feasible (all constraints satisfied) but the solution may not be the optimal integer solution.

For example if we round the LP solution given above to x₁=0, x₂=0, x₃=1, x₄=0 then all the constraints are satisfied and we have a feasible solution of value 0.5.

In fact for this particular (very small) problem this is not the optimal solution. In general we can say that the rounded LP relaxation solution is almost certainly non-optimal and may be very non-optimal (in the sense that the objective function value of the rounded LP relaxation solution is very far away from the objective function value of the optimal integer solution).

In general the solution process used in many LP based IP packages is

• specify the IP: objective, constraints, integer variables (typically x_j = integer between 0 and n).
• automatically generate the LP relaxation: same objective as IP, same constraints as IP with the addition of 0<=x_j<=n, variables as before but no longer required to be integer
• use the tree search procedure to generate the optimal solution to the IP.