Objectives
-
Find a cutting plane that removes part of the feasible set of a LOP without removing integer solutions.
-
Develop a method that uses cutting planes to solve an ILOP (Integer Linear Optimization Problem).
Section 4.2 Cutting Planes
A problem like Problem 4.1.3 does not result in an integer solution when the Simplex Method is used and in general, the simplex method does not solve these. In this section, we introduce cutting planes, which impose additional constraints on a problem that will reduce the feasible set without cutting away any integer solutions.
For example, the solution to Problem 4.1.3 is \((256,119)^{T}/60\approx (4.266,1.983)\) and \(z^{\star}=1619/60\approx 26.983\text{.}\) We found the solution to the ILOP at the end of the previous section by checking all integer solutions in the feasible set and using this technique, the optimal point is \((4,2)\) and \(z=26\text{.}\)
A cutting plane is an additional constraint that does not remove any integer solutions. For example, the constraints:
\begin{equation}
\begin{aligned} x_1 + x_2 \amp \leq 6 \\ x_1 +2x_2 \amp \leq 8.
\end{aligned}\tag{4.2.1}
\end{equation}
together with the constraints in Problem 4.1.3 would lead to the following feasible set:
Subsection 4.2.1 Finding Cutting Planes
\begin{align}
\amp \qquad \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] \notag\\
\begin{array}{r} 1 \mapsto 4,\\ 2 \mapsto 3, \end{array} \amp \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] \tag{4.2.2}
\end{align}
The solution to this \(\boldsymbol{x}^{\star}= (119, 256~|~0,0)^{T}/60\text{,}\) which is non-integral. The 1st row of the tableau in (4.2.2) is the equation:
\begin{equation*}
60 x_{2} +4x_{3} -17 x_{4} = 119
\end{equation*}
which can be rewritten by adding \(-4x_{3}-43x_{4}-60\) to both sides to get:
\begin{equation*}
60(x_{2} - x_{4} -1) = 59 - 4x_{3} -43x_{4}
\end{equation*}
And we are looking for integer values of \(x\)’s and since the left side is a multiple of 60, the right side must be as well. In addition, since \(x_{3}, x_{4} \geq 0\text{,}\) then the most it could be is 59, which is not a multiple of 60. Thus the left hand side can be at most 0. Therefore we include the constraint:
\begin{align*}
59-4x_{3}-43x_{4}\amp \leq 0 \amp \amp \text{or} \amp -4x_3 -43x_4 \amp \leq -59
\end{align*}
We then include this into the tableau by introducing the scaled slack variable \(60x_{5}\) to make the equation:
\begin{equation*}
-4x_{3}-43x_{4} + 60x_{5}= - 59
\end{equation*}
which generates the new tableau:
\begin{equation}
\left[\begin{array}{rr|rrrr|r} 0 \amp 60 \amp 4 \amp -17 \amp 0 \amp 0 \amp 119\\ 60 \amp 0 \amp -4 \amp 32 \amp 0 \amp 0 \amp 256\\ 0 \amp 0 \amp -4 \amp -43 \amp 60 \amp 0 \amp -59\\ \hline 0 \amp 0 \amp 4 \amp 43 \amp 0 \amp 60 \amp 1619\\ \end{array} \right]\tag{4.2.3}
\end{equation}
We now have a tableau that is infeasible and you might think that we need to use phase I of the simplex method to solve this and we do, but before doing this, bring \(x_{3}, x_{4}\) and \(x_{5}\) into the basis with
\begin{equation}
\begin{array}{r} 3 \mapsto 2, \\ 4 \mapsto 1, \end{array} \qquad \left[\begin{array}{rr|rrrr|r} 17 \amp 32 \amp 1 \amp 0 \amp 0 \amp 0 \amp 136\\ 4 \amp 4 \amp 0 \amp 1 \amp 0 \amp 0 \amp 25\\ 4 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 26\\ \hline -4 \amp -5 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]\tag{4.2.4}
\end{equation}
and notice that the third line of (4.2.3) is the new constraint, \(4x_1 + 5x_2 \leq 26\text{,}\) which is the cutting plane found above in which the variables are returned to the original \(x_1\) and \(x_2\text{.}\) If we graph all three constraints:
where the linear constraints are labelled by their slack variables. Notice that it appears that the \(x_5\) line has cut off some the feasible set leaving the integer points. Perhaps this cutting plane is enough to solve the ILOP Returning to (4.2.3), we use phase I to perform the matrix pivot about row 3, column 3 to get
1
However, an astute eye notices that the likely optimal vertex is left and above the known solution of \((4,2)\text{.}\)
\begin{equation}
3 \mapsto 5, \qquad \left[\begin{array}{rr|rrrr|r} 0 \amp 4 \amp 0 \amp -4 \amp 4 \amp 0 \amp 4\\ 4 \amp 0 \amp 0 \amp 5 \amp -4 \amp 0 \amp 21\\ 0 \amp 0 \amp 4 \amp 43 \amp -60 \amp 0 \amp 59\\ \hline 0 \amp 0 \amp 0 \amp 0 \amp 4 \amp 4 \amp 104\\ \end{array} \right]\tag{4.2.5}
\end{equation}
and this has the basic solution
\begin{equation*}
\boldsymbol{x} = \frac{1}{4} \left[\begin{array}{rr|rrr} 21 \amp 4 \amp 59 \amp 0 \amp 0 \end{array} \right]^{\intercal}
\end{equation*}
\begin{equation*}
4x_1 + 5x_4 -4x_5 = 21,
\end{equation*}
and add \(-x_{4} -20\) to both sides of the equation, one gets:
\begin{equation*}
4(x_1+x_4-x_5-5) = 1-x_4
\end{equation*}
and the left must be negative or \(-x_{4} \leq -1\text{.}\) This logic is similar to above in which a integer solution must be a multiple of 4 on the left side, so similar on the right. Since \(x_4 \geq 0\text{,}\) this means the right side can be no larger than zero. Introduce this into the tableau with a new slack variable \(4x_6\text{,}\) where the 4 is the pivot constant as seen in the rest of the tableau.
\begin{equation}
\left[\begin{array}{rr|rrrrr|r} 0 \amp 4 \amp 0 \amp -4 \amp 4 \amp 0 \amp 0 \amp 4\\ 4 \amp 0 \amp 0 \amp 5 \amp -4 \amp 0 \amp 0 \amp 21\\ 0 \amp 0 \amp 4 \amp 43 \amp -60 \amp 0 \amp 0 \amp 59\\ 0 \amp 0 \amp 0 \amp -1 \amp 0 \amp 4 \amp 0 \amp -1\\ \hline 0 \amp 0 \amp 0 \amp 0 \amp 4 \amp 0 \amp 4 \amp 104\\ \end{array} \right]\tag{4.2.6}
\end{equation}
and again before performing phase I, we bring \(x_{3}, x_{4}, x_{5}\) and \(x_{6}\) into the basis with
\begin{equation*}
\begin{array}{r}5 \mapsto 3 \\ 4 \mapsto 1 \\ 3 \mapsto 2 \end{array} \qquad \left[\begin{array}{rr|rrrrr|r} 17 \amp 32 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 136\\ 4 \amp 4 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 25\\ 4 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 26\\ 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 6\\ \hline -4 \amp -5 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and notice that the first three rows are those that appeared before and the fourth row is the new constraint \(x_1 + x_2 \leq 6\text{.}\)
\begin{equation*}
4 \mapsto 7, \qquad \left[\begin{array}{rr|rrrrr|r} 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp -4 \amp 0 \amp 2\\ 1 \amp 0 \amp 0 \amp 0 \amp -1 \amp 5 \amp 0 \amp 4\\ 0 \amp 0 \amp 1 \amp 0 \amp -15 \amp 43 \amp 0 \amp 4\\ 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp -4 \amp 0 \amp 1\\ \hline 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 26\\ \end{array} \right]
\end{equation*}
and this now has the basic solution
\begin{equation*}
\boldsymbol{x} = \left[\begin{array}{rr|rrrr}4 \amp 2 \amp 4 \amp 1 \amp 0 \amp 0 \end{array}\right]^{\intercal}
\end{equation*}
with objective value of \(z=26\) which is now integral, so this is the optimal solution to Problem 4.1.2. This also has the same solution as the geometric argument in Section 4.1
Subsection 4.2.2 Gomory’s Method
The techniques in Subsection 4.2.1 is formalized into what is called Gomory’s Method.
-
Set up the LOP and solve using the Simplex method.
-
If the solution is all integers, stop!! You have the solution.
-
If not, select the row with largest \(b_{i} \mod d\text{,}\) where \(b_{i}\) is the element in the last column and \(d\) is value of the basic variable. This is row \(i\text{.}\)
-
Determine a new inequality by rewriting the row \(i\) in step 3 by putting multiples of \(d\) on the left hand side and the remainders on the right (making sure each term is negative). Insert this new constraint into the tableau.
-
Solve the tableau using simplex method.
-
Goto step 2.
Let’s see this in action again with another example.
Problem 4.2.4.
Use Gomory’s method to solve the following:
\begin{equation*}
\begin{aligned} \text{Max.} \amp\amp z = 3x_1 +6x_2, \amp \\ \text{such that} \amp\amp x_1 + 7 x_2 \amp \leq 53, \\ \amp\amp 5 x_1 + 5 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 \amp \leq 65, \\ \amp\amp x_1, x_2 \amp \in \mathbb{N}_0 \end{aligned}
\end{equation*}
Solution.
First, the initial tableau for this problem is
\begin{equation*}
\left[\begin{array}{rr|rrrr|r} 1 \amp 7 \amp 1 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \amp 0 \amp 1 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 65\\ \hline -3 \amp -6 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and now perform the simplex method:
\begin{align*}
1 \mapsto 5\qquad \amp \left[\begin{array}{rr|rrrr|r} 0 \amp 56 \amp 8 \amp 0 \amp -1 \amp 0 \amp 359\\ 0 \amp 40 \amp 0 \amp 8 \amp -5 \amp 0 \amp 83\\ 8 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 65\\ \hline 0 \amp -48 \amp 0 \amp 0 \amp 3 \amp 8 \amp 195\\ \end{array} \right] \\
2 \mapsto 4 \qquad \amp \left[\begin{array}{rr|rrrr|r} 0 \amp 0 \amp 40 \amp -56 \amp 30 \amp 0 \amp 1214\\ 0 \amp 40 \amp 0 \amp 8 \amp -5 \amp 0 \amp 83\\ 40 \amp 0 \amp 0 \amp 0 \amp 5 \amp 0 \amp 325\\ \hline 0 \amp 0 \amp 0 \amp 48 \amp -15 \amp 40 \amp 1473\\ \end{array} \right]\\
5 \mapsto 3, \qquad\amp \left[\begin{array}{rr|rrrr|r} 0 \amp 0 \amp 40 \amp -56 \amp 30 \amp 0 \amp 1214\\ 0 \amp 30 \amp 5 \amp -1 \amp 0 \amp 0 \amp 214\\ 30 \amp 0 \amp -5 \amp 7 \amp 0 \amp 0 \amp 92\\ \hline 0 \amp 0 \amp 15 \amp 15 \amp 0 \amp 30 \amp 1560\\ \end{array} \right]
\end{align*}
which now has an optimal solution, however it is not integral. Now, we will add another constraint. We find \(b_{i} \mod d\text{,}\) where \(d=30\) and the top row has the largest value or 14. So we write down the top line and rearrange it to get a multiple of 30 of all terms on the left and ensure that the other variables have negative coefficients:
\begin{align*}
40 x_3-56 x_4 + 30 x_5 \amp = 1214 \\
30 x_5 -56x_4 -4 x_4 + 30 x_3 - 1200 \amp = 14 - 4x_4 - 10 x_3 \\
30 (x_5 - 2x_4 -x_3 -40) \amp = 14 - 4 x_4 - 10 x_3 \amp
\end{align*}
So the new constraint is \(14 - 4 x_{4} - 10 x_{3} \leq 0\) or \(-4 x_{4} -10x_{3} \leq -14\) and making it an equation with a slack variable (or \(d\) times this new variable)
\begin{equation*}
-5 x_3 - 2x_4 + 30 x_6 = -7
\end{equation*}
Now introduce this into the above tableau
\begin{equation*}
\left[\begin{array}{rr|rrrrr|r} 0 \amp 0 \amp 40 \amp -56 \amp 30 \amp 0 \amp 0 \amp 1214\\ 0 \amp 30 \amp 5 \amp -1 \amp 0 \amp 0 \amp 0 \amp 214\\ 30 \amp 0 \amp -5 \amp 7 \amp 0 \amp 0 \amp 0 \amp 92\\ 0 \amp 0 \amp -5 \amp -2 \amp 0 \amp 30 \amp 0 \amp -7\\ \hline 0 \amp 0 \amp 15 \amp 15 \amp 0 \amp 0 \amp 30 \amp 1560\\ \end{array} \right]
\end{equation*}
and again perform the simplex method:
\begin{equation*}
3 \mapsto 6, \qquad \left[\begin{array}{rr|rrrrr|r} 0 \amp 0 \amp 0 \amp -24 \amp 10 \amp 80 \amp 0 \amp 386\\ 0 \amp 10 \amp 0 \amp -1 \amp 0 \amp 10 \amp 0 \amp 69\\ 10 \amp 0 \amp 0 \amp 3 \amp 0 \amp -10 \amp 0 \amp 33\\ 0 \amp 0 \amp 10 \amp 4 \amp 0 \amp -60 \amp 0 \amp 14\\ \hline 0 \amp 0 \amp 0 \amp 3 \amp 0 \amp 30 \amp 10 \amp 513\\ \end{array} \right]
\end{equation*}
And this still does not have an integral solution, so we repeat another set of steps of Gomory’s method. We take the largest \(b_i \mod 10\) and this occurs in the 2nd row, therefore:
\begin{align*}
10x_2 - x_4 + 10x_6 \amp = 69 \\
10 (x_2 + x_6 - x_4-6) \amp = 9 - 9x_4
\end{align*}
and this new inequality is \(9-9x_4 \leq 0\) or \(-9x_4 \leq -9\text{.}\) Note that we can cancel the \(9\) on either side, but let’s leave it. Introducing a slack variable results in the new equation
\begin{equation*}
-9x_4 + 10 x_7 = -9
\end{equation*}
and introduce this into the tableau results in
\begin{equation*}
\left[\begin{array}{rr|rrrrrr|r} 0 \amp 0 \amp 0 \amp -24 \amp 10 \amp 80 \amp 0 \amp 0 \amp 386\\ 0 \amp 10 \amp 0 \amp -1 \amp 0 \amp 10 \amp 0 \amp 0 \amp 69\\ 10 \amp 0 \amp 0 \amp 3 \amp 0 \amp -10 \amp 0 \amp 0 \amp 33\\ 0 \amp 0 \amp 10 \amp 4 \amp 0 \amp -60 \amp 0 \amp 0 \amp 14\\ 0 \amp 0 \amp 0 \amp -9 \amp 0 \amp 0 \amp 10 \amp 0 \amp -9\\ \hline 0 \amp 0 \amp 0 \amp 3 \amp 0 \amp 30 \amp 0 \amp 10 \amp 513\\ \end{array} \right]
\end{equation*}
and performing the simplex method:
\begin{equation*}
4 \mapsto 8, \qquad \left[\begin{array}{rr|rrrrrr|r} 0 \amp 0 \amp 0 \amp 0 \amp 18 \amp 144 \amp -48 \amp 0 \amp 738\\ 0 \amp 18 \amp 0 \amp 0 \amp 0 \amp 18 \amp -2 \amp 0 \amp 126\\ 18 \amp 0 \amp 0 \amp 0 \amp 0 \amp -18 \amp 6 \amp 0 \amp 54\\ 0 \amp 0 \amp 18 \amp 0 \amp 0 \amp -108 \amp 8 \amp 0 \amp 18\\ 0 \amp 0 \amp 0 \amp 18 \amp 0 \amp 0 \amp -20 \amp 0 \amp 18\\ \hline 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 54 \amp 6 \amp 18 \amp 918\\ \end{array} \right]
\end{equation*}
The basic solution to this is
\begin{align*}
\boldsymbol{x} \amp = \frac{1}{18} \left[\begin{array}{rr|rrrrrr} 54 \amp 126 \amp 18 \amp 18 \amp 738 \amp 0 \amp 0 \end{array}\right]^{\intercal} \\
\amp = \left[\begin{array}{rr|rrrrrr} 3 \amp 7 \amp 1 \amp 1 \amp 41 \amp 0 \amp 0 \end{array}\right]^{\intercal}
\end{align*}
And this is now a integral solution, so this is the optimal solution to the ILOP.
The two problems we solved in this section only have 2 variables. This is nice in terms of plotting the feasible set, however let’s look at another problem with more variables.
Problem 4.2.5.
\begin{equation*}
\begin{aligned} \text{Max.} \amp\amp z = 3x_1 +6x_2 + 5 x_3, \amp\\ \text{such that} \amp\amp x_1 + 7 x_2 + 3x_3 \amp \leq 53, \\ \amp\amp 4 x_1 + 4 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 + 4x_3 \amp \leq 65, \\ \text{and} \amp\amp x_1, x_2, x_3 \amp \in \mathbb{N}_{0}.
\end{aligned}
\end{equation*}
Checkpoint 4.2.6.
Solve the ILOP in Problem 4.2.5 using Gomory’s method.
Solution.
First set up the initial tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 53\\ 4 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 65\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
perform standard phase II pivots, \(1 \mapsto 6, 2 \mapsto 5, 3 \mapsto 4, 5 \mapsto 1\)
\begin{equation*}
\left[\begin{array}{rrr|rrrr|r} 56 \amp 0 \amp 28 \amp 0 \amp 0 \amp 7 \amp 0 \amp 455\\ -20 \amp 28 \amp 0 \amp 4 \amp 0 \amp -3 \amp 0 \amp 17\\ 192 \amp 0 \amp 0 \amp -16 \amp 28 \amp 12 \amp 0 \amp 1360\\ \hline 76 \amp 0 \amp 0 \amp 24 \amp 0 \amp 17 \amp 28 \amp 2377\\ \end{array} \right]
\end{equation*}
THE REST OF THIS NEEDS TO BE REDONE!!!!!
To find a cutting plane, find the right column mod 28 and the largest one is in the 2nd row. We write down the equation:
\begin{equation*}
-20 x_1 + 28 x_2 + 4 x_4 - 3 x_6 = 17
\end{equation*}
The goal is now to make the left side a multiple of 28 (the slack variable coefficient) and to accomplish this, put parameters on the right side with coefficients that are negative and not less than \(-28\text{.}\) This is done by adding/subtracting appropriate multiples of terms.
\begin{equation*}
\begin{aligned} -20x_1 - 8x_1 + 28 x_2 - 3x_6 -25 x_6 \amp = 17 - 8x_1 - 4x_4 - 25 x_6 \\ 28 (-x_1 + x_2 - x_6) \amp = 17 - 8x_1 - 4x_4 - 25 x_6 \end{aligned}
\end{equation*}
and the new constraint is the right hand side needs to be 0 at most or
\begin{equation*}
-8x_1 -4x_4 -25 x_6 \leq -17
\end{equation*}
Add a slack variable to this in the form \(28x_7\) to this constraint:
\begin{equation*}
-8x_1 -4x_4 -25 x_6 +28 x_7 = -17
\end{equation*}
Add this to the tableau to get:
\begin{equation*}
\left[\begin{array}{rrr|rrrrr|r} 56 \amp 0 \amp 28 \amp 0 \amp 0 \amp 7 \amp 0 \amp 0 \amp 455\\ -20 \amp 28 \amp 0 \amp 4 \amp 0 \amp -3 \amp 0 \amp 0 \amp 17\\ 192 \amp 0 \amp 0 \amp -16 \amp 28 \amp 12 \amp 0 \amp 0 \amp 1360\\ -8 \amp 0 \amp 0 \amp -4 \amp 0 \amp -25 \amp 28 \amp 0 \amp -17\\ \hline 76 \amp 0 \amp 0 \amp 24 \amp 0 \amp 17 \amp 0 \amp 28 \amp 2377\\ \end{array} \right]
\end{equation*}
This is infeasible and the pivot \(1 \mapsto 7\) makes it feasible. Then the follow phase II pivots solve this LOP:
\begin{equation*}
\begin{array}{r} 4 \mapsto 2, \\ 6 \mapsto 1, \\ 2 \mapsto 4 \end{array} \qquad \left[\begin{array}{rrr|rrrrr|r} 48 \amp 0 \amp 25 \amp -1 \amp 0 \amp 0 \amp 7 \amp 0 \amp 402\\ -17 \amp 25 \amp 0 \amp 4 \amp 0 \amp 0 \amp -3 \amp 0 \amp 17\\ 168 \amp 0 \amp 0 \amp -16 \amp 25 \amp 0 \amp 12 \amp 0 \amp 1207\\ 8 \amp 0 \amp 0 \amp 4 \amp 0 \amp 25 \amp -28 \amp 0 \amp 17\\ \hline 63 \amp 0 \amp 0 \amp 19 \amp 0 \amp 0 \amp 17 \amp 25 \amp 2112\\ \end{array} \right]
\end{equation*}
This is optimal, but is not integral, so perform another step of Gomory’s method. Take the right column mod 25 and the largest value is rows 2 or 4. Since we always break a tie with a smaller index, we’ll take row 2 and write down the equation:
\begin{equation*}
-17 x_1 + 25 x_2 + 4 x_4 - 3 x_7 = 17
\end{equation*}
And again, we manipulate this equation to get the left side to be a multiple of the slack variable coefficient (25) with the parameter coefficients negative.
\begin{equation*}
\begin{aligned} -17 x_1 -8x_1 + 25 x_2 - 3 x_7 -22x_7 = 17 - 8x_1 - 4x_4 - 22x_7 \\ 25(-x_1 + x_2 - x_7) \amp = 17 - 8 x_1 - 4 x_4 - 22 x_7 \end{aligned}
\end{equation*}
The new constraint is that the right hand side is bounded above by 0 or
\begin{equation*}
- 8 x_1 - 4 x_4 - 22 x_7\leq -17
\end{equation*}
which including a slack variable \(25 x_8\) results in
\begin{equation*}
- 8 x_1 - 4 x_4 - 22 x_7 + 25x_8 = -17
\end{equation*}
resulting in the tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrrrr|r} 48 \amp 0 \amp 25 \amp -1 \amp 0 \amp 0 \amp 7 \amp 0 \amp 0 \amp 402\\ -17 \amp 25 \amp 0 \amp 4 \amp 0 \amp 0 \amp -3 \amp 0 \amp 0 \amp 17\\ 168 \amp 0 \amp 0 \amp -16 \amp 25 \amp 0 \amp 12 \amp 0 \amp 0 \amp 1207\\ 8 \amp 0 \amp 0 \amp 4 \amp 0 \amp 25 \amp -28 \amp 0 \amp 0 \amp 17\\ -8 \amp 0 \amp 0 \amp -4 \amp 0 \amp 0 \amp -22 \amp 25 \amp 0 \amp -17\\ \hline 63 \amp 0 \amp 0 \amp 19 \amp 0 \amp 0 \amp 17 \amp 0 \amp 25 \amp 2112\\ \end{array} \right]
\end{equation*}
The pivot \(1 \mapsto 8\) will make this tableau feasible and then one gets the following phase II pivots and resulting tableau
\begin{equation*}
\begin{array}{r} 4 \mapsto 2, \\ 7 \mapsto 1, \\ 2 \mapsto 4, \end{array} \qquad \left[\begin{array}{rrr|rrrrrr|r} 40 \amp 0 \amp 22 \amp -2 \amp 0 \amp 0 \amp 0 \amp 7 \amp 0 \amp 349\\ -14 \amp 22 \amp 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp -3 \amp 0 \amp 17\\ 144 \amp 0 \amp 0 \amp -16 \amp 22 \amp 0 \amp 0 \amp 12 \amp 0 \amp 1054\\ 16 \amp 0 \amp 0 \amp 8 \amp 0 \amp 22 \amp 0 \amp -28 \amp 0 \amp 34\\ 8 \amp 0 \amp 0 \amp 4 \amp 0 \amp 0 \amp 22 \amp -25 \amp 0 \amp 17\\ \hline 50 \amp 0 \amp 0 \amp 14 \amp 0 \amp 0 \amp 0 \amp 17 \amp 22 \amp 1847\\ \end{array} \right]
\end{equation*}
The basic solution of this tableau is not integral, so we perform another step. Take the right column mod 22 and the largest value is in the 3rd row. This row can be written as
\begin{equation*}
\begin{aligned} 144 x_1 -16x_4 + 22x_5 + 12 x_8 \amp = 1054 \\ 144 x_1 - 12x_1 - 16x_4 - 6x_4 + 22 x_5 - 47\cdot 22 \amp = 20 - 12x_1 - 6x_4 - 12 x_8 \\ 22 (6 x_1 - x_4 + x_5 - 47) \amp = 20 - 12x_1 - 6x_4 - 12 x_8 \end{aligned}
\end{equation*}
Again, the new constraint is that the left side needs to be bounded above by 0 or
\begin{equation*}
20 - 8x_1 - 6x_4 - 12 x_8 \leq 0.
\end{equation*}
Adding \(-8x_1 - 6x_4 - 12 x_7 + 22x_{9} = -20 \) to the tableau results in
\begin{equation*}
\left[\begin{array}{rrr|rrrrrrr|r} 40 \amp 0 \amp 22 \amp -2 \amp 0 \amp 0 \amp 0 \amp 7 \amp 0 \amp 0 \amp 349\\ -14 \amp 22 \amp 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp -3 \amp 0 \amp 0 \amp 17\\ 144 \amp 0 \amp 0 \amp -16 \amp 22 \amp 0 \amp 0 \amp 12 \amp 0 \amp 0 \amp 1054\\ 16 \amp 0 \amp 0 \amp 8 \amp 0 \amp 22 \amp 0 \amp -28 \amp 0 \amp 0 \amp 34\\ 8 \amp 0 \amp 0 \amp 4 \amp 0 \amp 0 \amp 22 \amp -25 \amp 0 \amp 0 \amp 17\\ -12 \amp 0 \amp 0 \amp -6 \amp 0 \amp 0 \amp -12 \amp 0 \amp 22 \amp 0 \amp -20\\ \hline 50 \amp 0 \amp 0 \amp 14 \amp 0 \amp 0 \amp 0 \amp 17 \amp 0 \amp 22 \amp 1847\\ \end{array} \right]
\end{equation*}
This is not feasible (as is true after every added constraint). First, \(1 \mapsto 9\) will make the above feasible and then the following will give a optimal tableau:
\begin{equation*}
\begin{array}{r} 4 \mapsto 1, \\ 8 \mapsto 4, \end{array} \qquad \left[\begin{array}{rrr|rrrrrrr|r} 18 \amp 0 \amp 12 \amp -3 \amp 0 \amp 0 \amp 0 \amp 0 \amp 7 \amp 0 \amp 184\\ -6 \amp 12 \amp 0 \amp 3 \amp 0 \amp 0 \amp 0 \amp 0 \amp -3 \amp 0 \amp 12\\ 72 \amp 0 \amp 0 \amp -12 \amp 12 \amp 0 \amp 0 \amp 0 \amp 12 \amp 0 \amp 564\\ 24 \amp 0 \amp 0 \amp 12 \amp 0 \amp 12 \amp 0 \amp 0 \amp -28 \amp 0 \amp 44\\ 18 \amp 0 \amp 0 \amp 9 \amp 0 \amp 0 \amp 12 \amp 0 \amp -25 \amp 0 \amp 32\\ 12 \amp 0 \amp 0 \amp 6 \amp 0 \amp 0 \amp 0 \amp 12 \amp -22 \amp 0 \amp 20\\ \hline 18 \amp 0 \amp 0 \amp 3 \amp 0 \amp 0 \amp 0 \amp 0 \amp 17 \amp 12 \amp 992\\ \end{array} \right]
\end{equation*}
This tableau’s basic solution is not integral, so we add another constraint. In this case, take the right column mod 12 and find the largest. Rows 4, 5 and 6 all have the same value of 8, so we take row 4 and write down the equation:
\begin{equation*}
\begin{aligned} 24 x_1 + 12x_4 + 12 x_6 - 28 x_9 \amp 44 \\
24 x_1 + 12 x_4 + 12 x_6 - 28 x_9 - 8 x_9 - 36 \amp = 8 -8 x_9 \\
12 (2x_1 + x_4 + x_6 - 3x_9) \amp = 8 - 8 x_9 \end{aligned}
\end{equation*}
\begin{equation*}
\left[\begin{array}{rrr|rrrrrrrr|r} 18 \amp 0 \amp 12 \amp -3 \amp 0 \amp 0 \amp 0 \amp 0 \amp 7 \amp 0 \amp 0 \amp 184\\ -6 \amp 12 \amp 0 \amp 3 \amp 0 \amp 0 \amp 0 \amp 0 \amp -3 \amp 0 \amp 0 \amp 12\\ 72 \amp 0 \amp 0 \amp -12 \amp 12 \amp 0 \amp 0 \amp 0 \amp 12 \amp 0 \amp 0 \amp 564\\ 24 \amp 0 \amp 0 \amp 12 \amp 0 \amp 12 \amp 0 \amp 0 \amp -28 \amp 0 \amp 0 \amp 44\\ 18 \amp 0 \amp 0 \amp 9 \amp 0 \amp 0 \amp 12 \amp 0 \amp -25 \amp 0 \amp 0 \amp 32\\ 12 \amp 0 \amp 0 \amp 6 \amp 0 \amp 0 \amp 0 \amp 12 \amp -22 \amp 0 \amp 0 \amp 20\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -8 \amp 12 \amp 0 \amp -8\\ \hline 18 \amp 0 \amp 0 \amp 3 \amp 0 \amp 0 \amp 0 \amp 0 \amp 17 \amp 0 \amp 12 \amp 992\\ \end{array} \right]
\end{equation*}
and then since this is in phase I, perform a pivot
\begin{equation*}
9 \mapsto 10, \qquad \left[\begin{array}{rrr|rrrrrrrr|r}
12 \amp 0 \amp 8 \amp -2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 7 \amp 0 \amp 118\\
-4 \amp 8 \amp 0 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -3 \amp 0 \amp 10\\
48 \amp 0 \amp 0 \amp -8 \amp 8 \amp 0 \amp 0 \amp 0 \amp 0 \amp 12 \amp 0 \amp 368\\
16 \amp 0 \amp 0 \amp 8 \amp 0 \amp 8 \amp 0 \amp 0 \amp 0 \amp -28 \amp 0 \amp 48\\
12 \amp 0 \amp 0 \amp 6 \amp 0 \amp 0 \amp 8 \amp 0 \amp 0 \amp -25 \amp 0 \amp 38\\
8 \amp 0 \amp 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp 8 \amp 0 \amp -22 \amp 0 \amp 28\\
0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 8 \amp -12 \amp 0 \amp 8\\ \hline
12 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 17 \amp 8 \amp 650\\
\end{array} \right]
\end{equation*}
This is optimal, but this is still not integral. Let’s try another step. Finding the last column modulo 8, the largest value is in rows 1 and 5. As is standard, with a tie, we’ll use the smaller indexed one or row 1, which can be written:
\begin{equation*}
\begin{aligned} 12 x_1 + 8 x_3 - 2x_4 + 7x_{10} \amp = 118 \\ 12 x_1 - 4x_1 + 8 x_3 -2x_4 - 6x_4 -112 \amp = 6 - 4x_1 - 6x_4 - 7x_{10} \\
8(x_1 + x_3 - x_4 - 14) \amp = 6 - 4x_1 - 6x_4 - 7x_{10} \end{aligned}
\end{equation*}
and the new constraint is that the right side is bounded above by 0, which is \(6 - 4x_1 -6x_4-7x_{10} \leq 0\) which can be written with a slack variable as \(-4x_1-6x_4-7x_{11} + 8x_{12} = -6\text{.}\) Adding this to the tableau is
\begin{equation*}
\left[\begin{array}{rrr|rrrrrrrrr|r}
12 \amp 0 \amp 8 \amp -2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 7 \amp 0 \amp 0 \amp 118\\
-4 \amp 8 \amp 0 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -3 \amp 0 \amp 0 \amp 10\\
48 \amp 0 \amp 0 \amp -8 \amp 8 \amp 0 \amp 0 \amp 0 \amp 0 \amp 12 \amp 0 \amp 0 \amp 368\\
16 \amp 0 \amp 0 \amp 8 \amp 0 \amp 8 \amp 0 \amp 0 \amp 0 \amp -28 \amp 0 \amp 0 \amp 48\\
12 \amp 0 \amp 0 \amp 6 \amp 0 \amp 0 \amp 8 \amp 0 \amp 0 \amp -25 \amp 0 \amp 0 \amp 38\\
8 \amp 0 \amp 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp 8 \amp 0 \amp -22 \amp 0 \amp 0 \amp 28\\
0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 8 \amp -12 \amp 0 \amp 0 \amp 8\\
-4 \amp 0 \amp 0 \amp -6 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -7 \amp 8 \amp 0 \amp -6\\ \hline
12 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 17 \amp 0 \amp 8 \amp 650\\
\end{array} \right]
\end{equation*}
Note that the last row is not feasible, so perform a pivot to make it feasible:
\begin{equation*}
1 \mapsto 11 \left[\begin{array}{rrr|rrrrrrrrr|r}
0 \amp 0 \amp 4 \amp -10 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -7 \amp 12 \amp 0 \amp 50\\
0 \amp 4 \amp 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 2 \amp -4 \amp 0 \amp 8\\
0 \amp 0 \amp 0 \amp -40 \amp 4 \amp 0 \amp 0 \amp 0 \amp 0 \amp -36 \amp 48 \amp 0 \amp 148\\
0 \amp 0 \amp 0 \amp -8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp -28 \amp 16 \amp 0 \amp 12\\
0 \amp 0 \amp 0 \amp -6 \amp 0 \amp 0 \amp 4 \amp 0 \amp 0 \amp -23 \amp 12 \amp 0 \amp 10\\
0 \amp 0 \amp 0 \amp -4 \amp 0 \amp 0 \amp 0 \amp 4 \amp 0 \amp -18 \amp 8 \amp 0 \amp 8\\
0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 4 \amp -6 \amp 0 \amp 0 \amp 4\\
4 \amp 0 \amp 0 \amp 6 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 7 \amp -8 \amp 0 \amp 6\\ \hline
0 \amp 0 \amp 0 \amp -8 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -2 \amp 12 \amp 4 \amp 316\\
\end{array} \right]
\end{equation*}
And then the following phase II pivots result in the optimal tableau:
\begin{equation*}
4 \mapsto 1 \left[\begin{array}{rrr|rrrrrrrrr|r}
10 \amp 0 \amp 6 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 7 \amp -2 \amp 0 \amp 90\\
-4 \amp 6 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -4 \amp 2 \amp 0 \amp 6\\
40 \amp 0 \amp 0 \amp 0 \amp 6 \amp 0 \amp 0 \amp 0 \amp 0 \amp 16 \amp -8 \amp 0 \amp 282\\
8 \amp 0 \amp 0 \amp 0 \amp 0 \amp 6 \amp 0 \amp 0 \amp 0 \amp -28 \amp 8 \amp 0 \amp 30\\
6 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 6 \amp 0 \amp 0 \amp -24 \amp 6 \amp 0 \amp 24\\
4 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 6 \amp 0 \amp -20 \amp 4 \amp 0 \amp 18\\
0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 6 \amp -9 \amp 0 \amp 0 \amp 6\\
4 \amp 0 \amp 0 \amp 6 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 7 \amp -8 \amp 0 \amp 6\\ \hline
8 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 11 \amp 2 \amp 6 \amp 486\\
\end{array} \right]
\end{equation*}
results in an optimal and integral tableau. The basic variable for this is
\begin{equation*}
\begin{aligned} \boldsymbol{x} \amp = \frac{1}{6} \left[\begin{array}{rrr|rrrrrrrrrrr} 0 \amp 6 \amp 90 \amp 6 \amp 282 \amp 30 \amp 24 \amp 18 \amp 6 \amp 0 \amp 0 \end{array}\right] \\ \amp = \left[\begin{array}{rrr|rrrrrrrrrrr} 0 \amp 1 \amp 15 \amp 1 \amp 47 \amp 5 \amp 4 \amp 3 \amp 1 \amp 0 \amp 0 \end{array}\right] \end{aligned}
\end{equation*}
and in the original variables, \(x_1 = 0, x_2 = 1\) and \(x_3=15\text{.}\) The objective value is 81.
This exercise showed how to apply Gomory’s method to a problem with more than two original variables. It also shows that often this takes many steps to reach an integer solution. Although it can be done “by hand”, this is done with software. See Chapter 5 and more specifically Section 5.5 for information of how to use the Julia language to solve these problems.
