|The Linear Programming
In the following we create a model with the Math Programming
add-in and solve it with the Jensen LP/IP solver add-in. We
first solve the model when the integrality condition is dropped,
thus obtaining a linear program (LP). This is a common practice
for very large models, because the linear program is much easier
to solve that the integer program (IP). We do it here to illustrate
some general relationships between the LP and the IP solution.
The LP solution is shown on the worksheet below. The solution
z = 40.9, A1 = 1, B3 = 1, B4 = 1, C1 = 1, C3
The solution uses the entire budget.
The LP model is called a relaxation
of the IP model, because one of the restrictions of the IP
model has been removed. One might be tempted to round the LP
solution to obtain an integer solution. In this case rounding
C3 up to 1 gives an infeasible solution because it violates
the budget constraint. Rounding C3 down to 0 gives a feasible
solution, but it is not optimal for the IP. In general, rounding
noninteger optimal LP solutions to integer ones will not provide
the optimum IP solution. In more complicated problems it is
often difficult to find a feasible solution by rounding.
We observe from the solution that although integrality was
not required, all the variables but one have integer values.
This is because the optimum LP solution is a basic solution,
and a basic solution has as many basic variables as there are
constraints. Every nonbasic variable is at either its upper
bound (1) or lower bound (0), while nonbasic variables may
assume fractional values. With only one constraint, one would
expect no more than one fractional value as we see here. It
is possible that a basic variable will assume one of its bounds.
Such a solution is called a degenerate solution. For degenerate
solutions, the number of values not equal to 0 or 1 will be
less than the number of constraints.
We note at the top of the Excel display that finding the LP
solution with the Jensen LP/IP solver required only 3 iterations
of the simplex method. Although the time indication is 0, it
is actually less than 1 second, the smallest number the time
field can display.
|The Integer Programming
We change the LP model into the IP model by re-imposing integrality.
The Excel model indicates this by prefacing the index of each
integer variable by the letter I. If only a subset of the variables
were required to be integer, only the ones in the subset would
have the I-preface. The solution as shown below has the values:
z = 40, A1 = 1, A3 = 1, B3 = 1, B4 = 1, C1
Comparing this solution to that
of the LP, we see that A3 has replaced C3 in the decision set,
with A3 having the value 1. The objective value has decreased
to 40. It will always be true that the optimal IP objective
value is no greater than the optimal LP objective value, because
the IP feasible region is more restrictive than the LP feasible
region. Because of the discrete nature of the solution, the
budget is not entirely used.
We also see that the IP solution takes much more computational
effort than the LP solution, requiring 132 simplex iterations,
compared to the 3 necessary to find the LP optimum. Although
the time required is only 1 second, this is an indication that
IP solutions will be much harder to come by than for the solution
for the LP model. Since the LP solution is guaranteed to be
at an extreme point of the feasible region (a basic solution),
we only need to consider 3 of these to find the solution. The
integer solution is usually not an extreme point, so a complicated
search process is necessary to locate it. The 70 tree nodes
shown above the time requirement is a measure of the difficulty
of this search. Compared to the 70 tree nodes explored there
is a much larger number of possible solutions to the model.
Considering all possible assignments of 0 or 1 to the 12 variables,
there are, in fact, 2 raised to the 12th power integer solutions
to this problem, 2096 solutions. Refer to the IP
Methods section of this site for more discussion about
the procedures for integer programming.