Welcome to this Graphical introduction to Integer Linear programming.

We will be exploring some properties of all-integer and mixed-integer linear models, and also

discuss binary (or 0-1) variables in a later video.

In an integer linear program, some or all decision variables are required to be integers

(or whole numbers). If all decision variables of an LP model are

required to be integer, we refer to that as an all-integer model –also referred to as

pure- or total-integer model. Consider this LP model, and its graph.

Here is the feasible region. Moving the objective function line upwards

(since this is a maximization problem), we see that the optimal solution occurs here,

at X = 1.59 and Y = 2.73, with a corresponding objective function value of 28.65.

Now suppose X actually represents the number of laptops,

and Y, the number desktops to purchase for a new office.

Since, by definition, X and Y can only assume integral values (or whole numbers), this is

an all-integer model. So to indicate that, we append the term “and

integer” to the model. The feasible solutions are now reduced only

to the points where both X and Y are integers simultaneously.

It follows that the feasible solutions to an all-integer problem are a collection of

dots. Moving the objective function line upwards

we see that the optimal solution to the all-integer problem occurs here at (0, 4), with an objective

function value of 28. That is, purchase no laptops and 4 desktops

for the office. Now suppose we decide ignore or relax the

integer requirements and use the best optimal solution satisfying the constraints, which

we saw earlier on as X = 1.59 and Y = 2.73 and Z = 28.65, we refer to that as LP relaxation.

So LP Relaxation simply means that we begin with an integer problem, and later ignore

the integer requirements when finding the solution to the problem.

As a result, LP Relaxation always provides an upper bound for the optimal value in a

maximization integer problem. In other words, the optimal value produced

by an integer problem cannot be better than that of its corresponding LP Relaxation problem.

That is, for a maximization problem, the optimal value of the integer problem will be less

or equal to that of its LP Relaxation. Now suppose X is still the number of laptops

to purchase, but Y is now the amount of time spent on the laptops.

Because only X now needs to be integer, we append “and X integer” to the model.

Since not all decision variables need to be integer, we refer to this as a mixed integer

problem. The feasible solutions are now a set of vertical

lines, showing that X must be an integer and Y can

assume any value on the vertical lines. So if we move the objective function line

upwards, we see that the optimal solution occurs here at X = 1 and Y = 3.2 with a corresponding

optimal value of Z = 28.4. Suppose instead, only Y is required to be

an integer and not X. Then we have another mixed integer problem.

In this case, the feasible solutions will be a set of horizontal lines, including this

point here at (0, 4). Moving the objective function line again we

see that the optimal solution occurs here at X = 1.25 and Y = 3, with an objective function

value of 28.5. Let’s now examine what could happen when

we round the optimal solution to the LP relaxation to obtain an integer solution.

Recall that the optimal solution to the LP relaxation problem is X = 1.59 and Y = 2.73

with an optimal objective function value of 28.65.

Recall also that the optimal all-integer solution occurs at (0, 4).

Rounding down the LP Relaxation solution gives X = 1, and Y=2 which is a feasible solution

but not optimal. So as long as all the coefficients in a maximization

problem are positive, rounding down the LP relaxation solution will always result in

a feasible solution, which as seen here, may not be optimal.

On the other hand, rounding up to the next higher integer gives X = 2, and Y=3 which

is not a feasible solution. Now consider this all-integer minimization

problem and its graph. The optimal solution to the LP relaxation

problem occurs here at X = 1.5 and Y = 2.5 with an objective function value of 19.

This provides a lower bound to the minimization integer problem.

That is, for a minimization problem, the optimal value of the integer problem will always be

greater or equal to that of its LP Relaxation. Moving the objective function line downwards,

we see that there are 2 optimal solutions to the integer problem. One at (0,5) and the

other at (2,2) with each producing an optimal value of 20.

Now, rounding down the LP Relaxation solution to this minimization problem gives X = 1,

and Y=2 which is not a feasible solution. On the other hand, rounding up to the next

higher integer gives X = 2, and Y=3 which is feasible but not optimal.

So as long as all the coefficients are positive, rounding up the LP relaxation solution in

a minimization problem will always result in a feasible solution, which may or may not

be optimal. And that concludes this graphical introduction

to integer linear programming. In the next video, I will be discussing the

applications of binary or 0-1 variables in integer linear programming.

Thanks for watching.