Objectives
-
Definition of an Integer Linear Optimization Problem.
-
Geometry of simple ILOPs.
-
Determine when solutions from simplex method are solutions to ILOPs.
Section 4.1 Introduction to Integer Linear Optimization Problems
In Section 2.1, we saw a few examples, where it was important that variables take on integer values. For example, the variables in Problem 2.1.1 are the number of toy cars, trucks and SUVs that Luis was going to make. It doesn’t make any sense to make half of a car for example, so it was important that these are integers.
The solution of this problem was to make 10 cars, 12 trucks and 15 SUVs. Perhaps we were lucky that the solution was an integer. We will see in this section that if we are "lucky" then we’re done.
Theorem 4.1.1.
Let \(P\) be an LOP in standard form with no integer constraints, and \(IP\) is the same LOP with integer constraints. If the optimal solution to \(P\) has an integer solution, then it is also the solution to \(IP\text{.}\)
Recall Problem 2.2.2 which had no integer constraints. The solution to this problem is \(\boldsymbol{x}^{\star}=(8,16)^{T}\) with \(z^{\star}= 56\text{.}\) If include another constraint of
\begin{equation*}
x_1, x_2 \in \mathbb{N}_0
\end{equation*}
is in included, then Problem 2.2.2 can be written
Problem 4.1.2. Integer LOP.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp \amp z = x_1 + 3x_2 \amp \\ \text{subject to} \amp \amp 4x_1 + 3x_2 \amp \leq 120, \\ \amp \amp x_1 + 2x_2 \amp \leq 40, \\ \amp \amp x_2 \amp \leq 16, \\ \text{and} \amp \amp x_1, x_2 \amp \in \mathbb{N}_0 \end{aligned}
\end{equation*}
then since Problem 2.2.2 has an integer solution then the same is a solution to Problem 4.1.2 or \(\boldsymbol{x}^{\star}=(8,16)^{T}\) with \(z^{\star}= 56\text{.}\)
However, what if we have an ILOP and the standard simplex method does not return an integer solution. As an example, consider the following LOP:
Problem 4.1.3.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp\amp z = 4x_1 + 5x_2 \amp \\ \text{s.t.}\amp\amp 17x_1+32x_2 \amp \leq 136, \\ \amp\amp 4x_1 + 4x_2 \amp \leq 25, \\ \text{and}\amp\amp x_1, x_2 \amp \in \mathbb{N}_0.
\end{aligned}
\end{equation*}
Let’s take a look at a plot of the feasible set here. The possible integer solutions are also plotted on the feasible set.
If the variables \(x_1\) and \(x_2\) are reals with \(x_1, x_2 \geq 0\text{,}\) then the feasible set is the quadrilateral shaded gray above. If the variables are nonnegative integers then the only options are the points plotted above.
Checkpoint 4.1.5.
Use the simplex method to solve Problem 4.1.3. Is the optimal solution consist only of integer points?
Solution.
This problem is in standard maximum form so we can write down the tableau.
\begin{equation*}
\left[\begin{array}{rr|rrr|r} 17 \amp 32 \amp 1 \amp 0 \amp 0 \amp 136\\ 4 \amp 4 \amp 0 \amp 1 \amp 0 \amp 25\\ \hline -4 \amp -5 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
Skipping some of the details, but using the simplex method, the next step is the tableau pivot \(1 \mapsto 4\) (matrix pivot about row 2, column 1):
\begin{equation*}
1 \mapsto 4 \qquad \left[\begin{array}{rr|rrr|r} 0 \amp 60 \amp 4 \amp -17 \amp 0 \amp 119\\ 4 \amp 4 \amp 0 \amp 1 \amp 0 \amp 25\\ \hline 0 \amp -4 \amp 0 \amp 4 \amp 4 \amp 100\\ \end{array} \right]
\end{equation*}
This is not optimal, so another pivot is done. The tableau pivot of \(2 \mapsto 3\) or the matrix pivot of row 1, column 2 results in
\begin{equation*}
2 \mapsto 3 \qquad \left[\begin{array}{rr|rrr|r} 0 \amp 60 \amp 4 \amp -17 \amp 0 \amp 119\\ 60 \amp 0 \amp -4 \amp 32 \amp 0 \amp 256\\ \hline 0 \amp 0 \amp 4 \amp 43 \amp 60 \amp 1619\\ \end{array} \right]
\end{equation*}
this is now optimal with basic solution
\begin{equation*}
\boldsymbol{x} = \frac{1}{60} \left[\begin{array}{rr|rr} 256 \amp 119 \amp 0 \amp 0 \end{array}\right]
\end{equation*}
and this is clearly not an integer solution.
As noted, in this case, the only possible integer points are those plotted in Figure 4.1.4. In the next exercise, we will use this fact to find the solution to the ILOP in Problem 4.1.3.
Checkpoint 4.1.6.
Note that the objective function, \(z = 4x_1 + 5x_2\) has positive coefficients for both \(x_1\) and \(x_2\text{.}\) This means that the objective increases as points go up and right. Evaluate the objective function at all integer points near the upper right edge of the feasible set. There should be 7 of these. Evaluate the objective value for each of these and this will solve Problem 4.1.2.
Solution.
We identify the integer points closest to the oblique lines that form the boundary of the feasible set. We also then evaluate the objective function at these points:
| \(x_1\) | \(x_2\) | \(z\) |
| 0 | 4 | 20 |
| 1 | 3 | 19 |
| 2 | 3 | 23 |
| 3 | 2 | 24 |
| 4 | 2 | 26 |
| 5 | 1 | 25 |
| 6 | 0 | 24 |
Finding the optimal solution using this technique often works for small problems (with a few variables), however as the problem increases in numbers of variables, the total number of points to be checked is not reasonable, so we seek other solution techniques.
In the next two sections, we will see two techniques that solve problems in which the optimal solution on the non-integer problem is not an integer. In both cases, the feasible set is changed to trim away these non-integer solutions.
