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. xi = 0 or 1 can be replaced by the two continuous constraints xi >= 0 and xi <= 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.2x1 + 0.3x2 + 0.5x3 + 0.1x4

subject to

0.5x1 + 1.0x2 + 1.5x3 + 0.1x4 <= 3.1

0.3x1 + 0.8x2 + 1.5x3 + 0.4x4 <= 2.5

0.2x1 + 0.2x2 + 0.3x3 + 0.1x4 <= 0.4

xj <= 1 j=1,...,4

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

If we solve this LP then:

However for the LP relaxation of the capital budgeting problem the LP solution is x1=0, x2=0.5, x3=1, x4=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:

For example if we round the LP solution given above to x1=0, x2=1, x3=1, x4=0 then the constraints relating to the amount of available capital in year 3 is violated.

For example if we round the LP solution given above to x1=0, x2=0, x3=1, x4=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