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.

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_{1} + 0.3x_{2} + 0.5x_{3} + 0.1x_{4}

subject to

0.5x_{1} + 1.0x_{2} + 1.5x_{3} + 0.1x_{4}
<= 3.1

0.3x_{1} + 0.8x_{2} + 1.5x_{3} + 0.4x_{4}
<= 2.5

0.2x_{1} + 0.2x_{2} + 0.3x_{3} + 0.1x_{4}
<= 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_{1}=0, x_{2}=0.5, x_{3}=1, x_{4}=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_{1}=0,
x_{2}=1, x_{3}=1, x_{4}=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_{1}=0,
x_{2}=0, x_{3}=1, x_{4}=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.