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.