Objectives
-
Take a feasible set that contains a non-integer solution and divide it into two feasible set.
-
Use this technique to solve ILOPs called Branch and Bound.
Section 4.3 Branch and Bound
In Section 4.2, we solved Problem 4.1.3 using Gomory’s cutting plane method. An alternative technique called branch and bound is introduced in this section. In short, the branch and bound method uses the simplex method and if an non-integral solution arises, we cut the feasible set in two sets which will exclude the non-integral solution. This is done in a systematic way to arrive at the desired answer. Let’s dive into this method with an example.
Recall that above we solved Problem 4.1.3 using the simplex method. The result was \(\boldsymbol{x}^{\star}=(256,119)^{T}/60\approx (4.266,1.983)\) and \(z^{\star}=1619/60\approx 26.983\text{.}\)
The basic idea presented here is to split each of the feasible sets into smaller regions with boundaries as integers. For example, since \(x_{1}^{\star}=4.266\) from above we solve two new problems, one of which has the constraint that \(x_{1} \leq 4\) and the other has the constraint \(x_{1} \geq 5\text{.}\) That is there are two problems:
Problem 4.3.1. LOP A.
\begin{equation*}
\begin{aligned} \text{Max.} \amp\amp z = 4x_1 + 5x_2, \amp \\ \text{such that}\amp\amp 17x_1+32x_2 \amp\leq 136, \\ \amp\amp 4x_1 + 4x_2 \amp\leq 25, \\ \amp\amp x_1 \amp \leq 4, \\ \text{and}\amp\amp x_1, x_2 \amp \in \mathbb{N}_0.
\end{aligned}
\end{equation*}
Problem 4.3.2. LOP B.
\begin{equation*}
\begin{aligned} \text{Max.} \amp\amp z = 4x_1 + 5x_2, \amp \\ \text{such that}\amp\amp 17x_1+32x_2 \amp\leq 136, \\ \amp\amp 4x_1 + 4x_2 \amp\leq 25, \\ \amp\amp x_1 \amp \geq 5, \\ \text{and}\amp\amp x_1, x_2 \amp \in \mathbb{N}_0.
\end{aligned}
\end{equation*}
Both LOP A and LOP B have the nonnegative constraint and the same objective function. Solving each via the simplex method we have the solutions to LOP A and B respectively.
1
For this section, we are skipping the details of the simplex method that we have seen earlier in the text and focus on the bigger picture.
What we have done is split the original problem into two which can be visualized as follows:
The solution to these two problems is
\begin{align*}
\amp \text{LOP A} \amp \amp \text{LOP B} \\
x_1^{\star} \amp = 4 \amp x_1^{\star} \amp = 5 \\
x_2^{\star} \amp = 68/32 \approx 2.125 \amp x_2^{\star} \amp = 5/4 = 1.25 \\
z^{\star} \amp = 852/32 \amp z^{\star} \amp = 105/4
\end{align*}
Note that the optimal solution of LOP A is the upper right corner of \(F_A\) and the optimal solution of LOP B is the upper left corner of \(F_B\text{.}\) These don’t quite fall on integers.
Since neither solution is integral, we next need to split each problem again, this time using \(x_{2}\text{.}\) For problem LOP A, we solve with the two constraints: \(x_{2} \leq 2\) and then \(x_{2} \geq 3\text{.}\) We will call these LOP AA and LOP AB:
Problem 4.3.4. LOP AA.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp\amp z = 4x_1 + 5x_2 \amp \\ \text{such that}\amp\amp 17x_1+32x_2 \amp\leq 136, \\ \amp\amp 4x_1 + 4x_2 \amp\leq 25, \\ \amp\amp x_1 \amp \leq 4, \\ \amp\amp x_2 \amp \leq 2, \\ \text{and}\amp\amp x_1, x_2 \amp \in \mathbb{N}_0.
\end{aligned}
\end{equation*}
Problem 4.3.5. LOP AB.
\begin{equation*}
\begin{aligned} \text{Maximize.} \amp\amp z = 4x_1 + 5x_2 \amp \\ \text{such that}\amp\amp 17x_1+32x_2 \amp\leq 136, \\ \amp\amp 4x_1 + 4x_2 \amp\leq 25, \\ \amp\amp x_1 \amp \leq 4, \\ \amp\amp x_2 \amp \geq 3, \\ \text{and}\amp\amp x_1, x_2 \amp \in \mathbb{N}_0.
\end{aligned}
\end{equation*}
Similarly, LOP B can be split into two problems. Since the solution to LOP B contains \(x_{2}^{\star}=1.25\text{,}\) the split is \(x_{2} \leq 1\) and \(x_{2} \geq 2\text{.}\) The two problems are:
Problem 4.3.6. LOP BA.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp\amp z = 4x_1 + 5x_2 \amp \\ \text{such that}\amp\amp 17x_1+32x_2 \amp\leq 136, \\ \amp\amp 4x_1 + 4x_2 \amp\leq 25, \\ \amp\amp x_1 \amp \geq 5, \\ \amp\amp x_2 \amp \leq 1, \\ \text{and}\amp\amp x_1, x_2 \amp \in \mathbb{N}_0.
\end{aligned}
\end{equation*}
Problem 4.3.7. LOP BB.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp\amp z = 4x_1 + 5x_2 \amp \\ \text{such that}\amp\amp 17x_1+32x_2 \amp\leq 136, \\ \amp\amp 4x_1 + 4x_2 \amp\leq 25, \\ \amp\amp x_1 \amp \geq 5, \\ \amp\amp x_2 \amp \geq 2, \\ \text{and}\amp\amp x_1, x_2 \amp \in \mathbb{N}_0.
\end{aligned}
\end{equation*}
Again, we have split each of the feasible sets into 2:
We now solve all four of these subproblems using the simplex method.
\begin{align*}
\text{LOP AA} \amp\amp\text{LOP AB} \amp \amp \text{LOP BA}\\
x_1^{\star} \amp = 4, \amp x_1^{\star} \amp = 40/17\approx 2.353, \amp x_1^{\star} \amp = 21/4 =5.25, \\
x_2^{\star} \amp = 2, \amp x_2^{\star} \amp = 3, \amp x_2^{\star} \amp =1, \\
z^{\star} \amp = 26, \amp z^{\star} \amp = 415/17 \approx 24.411, \amp z^{\star} \amp = 26.
\end{align*}
There is no solution to LOP BB, which shouldn’t be a surprise looking at the feasible set in Figure 4.3.8 in that \(F_{BB}\) is empty. Also, note that we have our first integer solution for problem LOP AA. This is a potential solution and importantly, the optimal solution would have a value greater than 26. Thus, if any solution has value smaller than 26, we can ignore that. For example, any integer solution to LOP AB will be smaller than 24.411 and which is clearly smaller than 26.
At this point we can stop because any integer solution that is a subset of \(F_{BA}\) will has a solution no more that 26. Since we are looking for a solution, there may be another integer solution in this set, but we already have one.
Subsection 4.3.1 A Branch and Bound Flowchart
You can see from the previous example that this continued splitting can be difficult to follow. It’s helpful to build a flowchart of this situation. The following shows the solution to the Problem 4.1.3 using branch and bound.
Subsection 4.3.2 Systematic Branch and Bound Algorithm
The key to this method is the splitting step, in which the feasible set on variable \(i\) is split into two pieces. Problem \(PA\) will be \(P\) with the additional constraint \(x_i \leq \lfloor \hat{x}_i \rfloor\text{.}\) Problem \(PB\) will have the same constraints as \(P\) with the additional one \(x_i \geq \lceil \hat{x}_i \rceil\text{.}\)
The following steps will result in finding an integer solution to an LOP. Call this \(P\)
-
Solve \(P\) using the simplex method. If the optimal point is integral, stop, this is a possible solution.
-
If the solution to \(P\) is not integral, let \(x_i\) be the smallest indexed non-integer solution. Perform the splitting step and solve both \(PA\) and \(PB\text{.}\)
-
If \(PA\) has an integer solution, note it’s objective value. If not repeat step #2.
-
If \(PB\) has an integer solution, note it’s objective value. If not repeat step #2.
-
Once all branches have resulted in integer solutions, is feasible or has an objective value smaller than the objective of a integer solution. Select the largest integer for the solution.
In Section 4.2, we solved a ILOP with three variables. The following exercise finds the solution to Problem 4.2.5 using the branch and bound technique.
Checkpoint 4.3.10.
Solve Problem 4.2.5 using the branch and bound algorithm.
Solution.
The problem is in standard form, so we just write down the tableau as
\begin{equation*}
\left[\begin{array}{rrr|rrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \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 64\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and then perform the following pivots (again not showing all of the details)
\begin{equation*}
\begin{array}{r} 3 \mapsto 6, \\ 2 \mapsto 4, \end{array} \qquad \left[\begin{array}{rrr|rrrr|r} -20 \amp 28 \amp 0 \amp 4 \amp 0 \amp -3 \amp 0 \amp 20\\ 240 \amp 0 \amp 0 \amp -20 \amp 28 \amp 15 \amp 0 \amp 1328\\ 56 \amp 0 \amp 28 \amp 0 \amp 0 \amp 7 \amp 0 \amp 448\\ \hline 76 \amp 0 \amp 0 \amp 24 \amp 0 \amp 17 \amp 28 \amp 2360\\ \end{array} \right]
\end{equation*}
This has the basic solution
\begin{equation*}
\begin{aligned} \boldsymbol{x} \amp = \frac{1}{28}\left[ \begin{array}{rrr|rrr} 0 \amp 20 \amp 448 \amp 0 \amp 1328 \amp 0 \end{array} \right] \\ \amp \approx \left[ \begin{array}{rrr|rrr} 0 \amp 0.714 \amp 16 \amp 0 \amp 47.43 \amp 0 \end{array} \right] \end{aligned}
\end{equation*}
So this is not integral, so we will form two problems. This solution has \(x_1=0\text{,}\) which is an integer, so start with \(x_2\) and add the two constraints: \(x_2 \leq 0\) and \(x_2 \geq 1\) in order to eliminate the current solution for \(x_2\text{.}\) These problems are
Problem 4.3.11. PA.
\begin{equation*}
\begin{aligned} \text{Maximize} \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 5 x_1 + 5 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 + 4x_3 \amp \leq 65, \\ \amp \amp x_2 \amp \leq 0, \\ \text{and} \amp\amp x_1, x_2, x_3 \amp \in \mathbb{N}_{0}.
\end{aligned}
\end{equation*}
Problem 4.3.12. PB.
\begin{equation*}
\begin{aligned} \text{Maximize} \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 5 x_1 + 5 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 + 4x_3 \amp \leq 65, \\ \amp \amp x_2 \amp \geq 1, \\ \text{and} \amp\amp x_1, x_2, x_3 \amp \in \mathbb{N}_0.
\end{aligned}
\end{equation*}
The solution to PA is found by starting with the simplex tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 64\\ 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and then perform the following pivots to get the optimal tableau:
\begin{equation*}
\begin{array}{r} 3 \mapsto 6, \\ 2 \mapsto 7, \end{array} \qquad \left[\begin{array}{rrr|rrrrr|r} -20 \amp 0 \amp 0 \amp 4 \amp 0 \amp -3 \amp -28 \amp 0 \amp 20\\ 20 \amp 0 \amp 0 \amp 0 \amp 4 \amp 0 \amp -20 \amp 0 \amp 204\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 64\\ 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp 0 \amp 4 \amp 0 \amp 0\\ \hline 28 \amp 0 \amp 0 \amp 0 \amp 0 \amp 5 \amp 24 \amp 4 \amp 320\\ \end{array} \right]
\end{equation*}
and this has the optimal solution:
\begin{equation*}
\begin{aligned} \boldsymbol{x} \amp = \frac{1}{4} \left[\begin{array}{rrr|rrrr} 0 \amp 0 \amp 65 \amp 17 \amp 204 \amp 0 \amp 0 \end{array}\right] \\ \amp = \left[\begin{array}{rrr|rrrr} 0 \amp 0 \amp 16.25 \amp 4.25 \amp 51 \amp 0 \amp 0 \end{array}\right] \end{aligned}
\end{equation*}
which is not integral.
Next, return to the simplex tableau corresponding to problem PB, which has the following simplex tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 64\\ 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp -1\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
where note that the inequality \(x_2 \geq 1\) has been put into standard form.
The pivots that first make the tableau feasible, then finds the optimal solution are
\begin{equation*}
\begin{array}{r} 2 \mapsto 7, \\ 1 \mapsto 6, \\ 3 \mapsto 4, \end{array} \qquad \left[\begin{array}{rrr|rrrrr|r} 0 \amp 0 \amp 20 \amp 8 \amp 0 \amp -1 \amp 56 \amp 0 \amp 304\\ 0 \amp 0 \amp 0 \amp 20 \amp 20 \amp -15 \amp 240 \amp 0 \amp 880\\ 20 \amp 0 \amp 0 \amp -4 \amp 0 \amp 3 \amp -28 \amp 0 \amp 8\\ 0 \amp 20 \amp 0 \amp 0 \amp 0 \amp 0 \amp -20 \amp 0 \amp 20\\ \hline 0 \amp 0 \amp 0 \amp 28 \amp 0 \amp 4 \amp 76 \amp 20 \amp 1664\\ \end{array} \right]
\end{equation*}
which has the basic solution
\begin{equation*}
\begin{aligned} \boldsymbol{x} = \amp \frac{1}{20} \left[ \begin{array}{rrr|rrrr} 8 \amp 20 \amp 304 \amp 0 \amp 880 \amp 0 \amp 0 \end{array} \right] \\ \approx \amp \left[ \begin{array}{rrr|rrrr} 0.4 \amp 1 \amp 15.2 \amp 0 \amp 44 \amp 0 \amp 0 \end{array} \right] \end{aligned}
\end{equation*}
which is not integral. We need to do another level. First, let’s define PAA and PAB as the two problems that split the feasible set of PA. Since \(x_1\) and \(x_2\) are both integers, we will split the feasible set of PAA using \(x_3\) and the two constraints \(x_3 \leq 16\) and \(x_3 \geq 17\text{.}\)
Problem 4.3.13. PAA.
\begin{equation*}
\begin{aligned} \text{Maximize} \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 5 x_1 + 5 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 + 4x_3 \amp \leq 65, \\ \amp\amp x_2 \amp \leq 0, \\ \amp \amp x_3 \amp \geq 17, \\ \text{and} \amp\amp x_1, x_2, x_3 \amp \in \mathbb{N}_{0}.
\end{aligned}
\end{equation*}
Problem 4.3.14. PAB.
\begin{equation*}
\begin{aligned} \text{Maximize} \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 5 x_1 + 5 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 + 4x_3 \amp \leq 65, \\ \amp\amp x_2 \amp \leq 0, \\ \amp \amp x_3 \amp \leq 16, \\ \text{and} \amp\amp x_1, x_2, x_3 \amp \in \mathbb{N}_{0}.
\end{aligned}
\end{equation*}
The solution to PAA is found by starting with the simplex tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 64\\ 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp -17\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and then one pivot results in the tableau
\begin{equation*}
3 \mapsto 8, \qquad \left[\begin{array}{rrr|rrrrrr|r} 1 \amp 7 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 3 \amp 0 \amp 2\\ 5 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 4 \amp 0 \amp -4\\ 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp -1 \amp 0 \amp 17\\ \hline -3 \amp -6 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -5 \amp 1 \amp 85\\ \end{array} \right]
\end{equation*}
and from the 3rd row, there is no positive ratio of last column to parameter coefficients, so this tableau is infeasible.
Next, return to the simplex tableau corresponding to problem PAB, which has the following simplex tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 64\\ 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 16\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
Applying the simplex method, we arrive at the following tableau:
\begin{equation*}
\begin{array}{r} 3 \mapsto 6, \\ 2 \mapsto 7, \end{array} \qquad \left[\begin{array}{rrr|rrrrrr|r} -20 \amp 0 \amp 0 \amp 4 \amp 0 \amp -3 \amp -28 \amp 0 \amp 0 \amp 20\\ 20 \amp 0 \amp 0 \amp 0 \amp 4 \amp 0 \amp -20 \amp 0 \amp 0 \amp 204\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 64\\ 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp 0 \amp 4 \amp 0 \amp 0 \amp 0\\ -8 \amp 0 \amp 0 \amp 0 \amp 0 \amp -1 \amp 0 \amp 4 \amp 0 \amp 0\\ \hline 28 \amp 0 \amp 0 \amp 0 \amp 0 \amp 5 \amp 24 \amp 0 \amp 4 \amp 320\\ \end{array} \right]
\end{equation*}
which has the basic solution
\begin{equation*}
\begin{aligned} \boldsymbol{x} \amp = \frac{1}{4} \left[\begin{array}{rrr|rrrrr} 0 \amp 0 \amp 64 \amp 20 \amp 204 \amp 0 \amp 0 \end{array}\right] \\ \amp = \left[\begin{array}{rrr|rrrr} 0 \amp 0 \amp 16 \amp 5 \amp 51 \amp 0 \amp 0 \end{array}\right] \end{aligned}
\end{equation*}
which is an integer solution. The objective value of this solution is \(320/4=80\text{.}\)
Next, the problem PB is split into two problems, PBA and PBB, where the feasible set of PBA is split using \(x_1 \leq 0\) and \(x_1 \geq 1\text{.}\)
Problem 4.3.15. PBA.
\begin{equation*}
\begin{aligned} \text{Maximize} \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 5 x_1 + 5 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 + 4x_3 \amp \leq 65, \\ \amp\amp x_2 \amp \geq 1, \\ \amp\amp x_1 \amp \leq 0, \\ \text{and} \amp\amp x_1, x_2, x_3 \amp \in \mathbb{N}_{0}.
\end{aligned}
\end{equation*}
Problem 4.3.16. PBB.
\begin{equation*}
\begin{aligned} \text{Maximize} \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 5 x_1 + 5 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 + 4x_3 \amp \leq 65, \\ \amp\amp x_2 \amp \geq 1, \\ \amp\amp x_1 \amp \geq 1, \\ \text{and} \amp\amp x_1, x_2, x_3 \amp \in \mathbb{N}_{0}.
\end{aligned}
\end{equation*}
The solution to PBA is found by starting with the simplex tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 64\\ 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp -1\\ 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and then apply the simplex method to get the following tableau:
\begin{equation*}
\begin{array}{r} 2 \mapsto 7, \\ 1 \mapsto 8, \\ 3 \mapsto 4, \end{array} \qquad \left[\begin{array}{rrr|rrrrrr|r} 0 \amp 0 \amp 3 \amp 1 \amp 0 \amp 0 \amp 7 \amp -1 \amp 0 \amp 46\\ 0 \amp 0 \amp 0 \amp 0 \amp 3 \amp 0 \amp 15 \amp -15 \amp 0 \amp 138\\ 0 \amp 0 \amp 0 \amp -4 \amp 0 \amp 3 \amp -28 \amp -20 \amp 0 \amp 8\\ 0 \amp 3 \amp 0 \amp 0 \amp 0 \amp 0 \amp -3 \amp 0 \amp 0 \amp 3\\ 3 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 3 \amp 0 \amp 0\\ \hline 0 \amp 0 \amp 0 \amp 5 \amp 0 \amp 0 \amp 17 \amp 4 \amp 3 \amp 248\\ \end{array} \right]
\end{equation*}
The basic solution of this tableau is
\begin{equation*}
\begin{aligned} \boldsymbol{x} \amp = \frac{1}{3} \left[\begin{array}{rrr|rrrrr} 0 \amp 3 \amp 46 \amp 0 \amp 138 \amp 8 \amp 0 \end{array}\right] \\ \amp \approx \left[\begin{array}{rrr|rrrr} 0 \amp 1 \amp 15.33 \amp 0 \amp 46 \amp 0 \end{array}\right] \end{aligned}
\end{equation*}
which is not integral. Also, note that the objective value of this tableau is \(248/3\approx 82.667\text{,}\) which is greater than the objective value of problem PAB. This branch needs to be further explored.
Return to Problem PBB, which has the following simplex tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 64\\ 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp -1\\ -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp -1\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
And then applying the simplex method, we arrive at the following tableau:
\begin{equation*}
\begin{array}{r} 1 \mapsto 8, \\ 2 \mapsto 7, \\ 3 \mapsto 6, \\ 7 \mapsto 4 \end{array} \qquad \left[\begin{array}{rrr|rrrrrr|r} 0 \amp 0 \amp 0 \amp 4 \amp 0 \amp -3 \amp 28 \amp -20 \amp 0 \amp 12\\ 0 \amp 0 \amp 0 \amp -20 \amp 28 \amp 15 \amp 0 \amp 240 \amp 0 \amp 1088\\ 0 \amp 0 \amp 28 \amp 0 \amp 0 \amp 7 \amp 0 \amp 56 \amp 0 \amp 392\\ 0 \amp 28 \amp 0 \amp 4 \amp 0 \amp -3 \amp 0 \amp -20 \amp 0 \amp 40\\ 28 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -28 \amp 0 \amp 28\\ \hline 0 \amp 0 \amp 0 \amp 24 \amp 0 \amp 17 \amp 0 \amp 76 \amp 28 \amp 2284\\ \end{array} \right]
\end{equation*}
and this has the basic solution
\begin{equation*}
\begin{aligned} \boldsymbol{x} \amp = \frac{1}{28} \left[\begin{array}{rrr|rrrrr} 28 \amp 40 \amp 392 \amp 0 \amp 1088 \amp 0 \amp 12 \amp 0 \end{array}\right] \\ \amp \approx \left[\begin{array}{rrr|rrrr} 1 \amp 1.43 \amp 14 \amp 0 \amp 38.86 \amp 0 \amp 0.43 \end{array}\right] \end{aligned}
\end{equation*}
Which is not integral, and has an objective value of \(2284/28\approx 81.571\text{.}\) This is greater than the objective value of problem PAB, so we should explore this branch as well.
Problem 4.3.17. PBAA.
\begin{equation*}
\begin{aligned} \text{Maximize} \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 5 x_1 + 5 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 + 4x_3 \amp \leq 65, \\ \amp\amp x_2 \amp \geq 1, \\ \amp\amp x_1 \amp \leq 0, \\ \amp \amp x_3 \amp \leq 15, \\ \text{and} \amp\amp x_1, x_2, x_3 \amp \in \mathbb{N}_{0}.
\end{aligned}
\end{equation*}
Problem 4.3.18. PBAB.
\begin{equation*}
\begin{aligned} \text{Maximize} \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 5 x_1 + 5 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 + 4x_3 \amp \leq 65, \\ \amp\amp x_2 \amp \geq 1, \\ \amp\amp x_1 \amp \leq 0, \\ \amp \amp x_3 \amp \geq 16, \\ \text{and} \amp\amp x_1, x_2, x_3 \amp \in \mathbb{N}_{0}.
\end{aligned}
\end{equation*}
The solution to PBAA is found by starting with the simplex tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrrrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 64\\ 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp -1\\ 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 15\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and then applying the simplex method, we arrive at the following tableau:
\begin{equation*}
\begin{array}{r} 2 \mapsto 7, \\ 1 \mapsto 8, \\ 3 \mapsto 9, \\ 7 \mapsto 4, \end{array} \qquad \left[\begin{array}{rrr|rrrrrrr|r} 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 7 \amp -1 \amp -3 \amp 0 \amp 1\\ 0 \amp 0 \amp 0 \amp -5 \amp 7 \amp 0 \amp 0 \amp -30 \amp 15 \amp 0 \amp 317\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 7 \amp 0 \amp -56 \amp -28 \amp 0 \amp 28\\ 0 \amp 7 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp -1 \amp -3 \amp 0 \amp 8\\ 7 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 7 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp 7 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 7 \amp 0 \amp 105\\ \hline 0 \amp 0 \amp 0 \amp 6 \amp 0 \amp 0 \amp 0 \amp 15 \amp 17 \amp 7 \amp 573\\ \end{array} \right]
\end{equation*}
and this has the basic solution
\begin{equation*}
\begin{aligned} \boldsymbol{x} \amp = \frac{1}{7} \left[\begin{array}{rrr|rrrrrr} 0 \amp 8 \amp 105 \amp 0 \amp 317 \amp 28 \amp 0 \amp \end{array}\right] \\ \amp \approx \left[\begin{array}{rrr|rrrr} 0 \amp 1.143 \amp 15 \amp 0 \amp 45.29 \amp 4 \amp 0 \end{array}\right].
\end{aligned}
\end{equation*}
This is not integral, and the objective value of this tableau is \(573/7\approx 81.857\text{,}\) which is greater than the objective value of problem PAB. This may still have a viable solution. We will explore this below.
Next, the solution to PBAB is found by starting with the simplex tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrrrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 64\\ 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp -1\\ 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp -16\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and applying the simplex method, we arrive at the following tableau:
\begin{equation*}
\begin{array}{r} 2 \mapsto 7, \\ 3 \mapsto 9, \end{array} \qquad \left[\begin{array}{rrr|rrrrrrr|r} 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 7 \amp 0 \amp 3 \amp 0 \amp -2\\ 5 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 5 \amp 0 \amp 0 \amp 0 \amp 46\\ 8 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 4 \amp 0 \amp 0\\ 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 1\\ 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -1 \amp 0 \amp 16\\ \hline -3 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp -6 \amp 0 \amp -5 \amp 1 \amp 86\\ \end{array} \right]
\end{equation*}
and the top row shows that this tableau is infeasible. Therefore, this branch is not explored further.
There is still the branch based on PBAA, so we split the feasible set of PBAA using \(x_2 \leq 1\) and \(x_2 \geq 2\text{.}\) The second inequality here is redundant here, since \(x_2 \geq 1\) is already a constraint in PBAA, so a problem PBAAB will not be created.
Problem 4.3.19. PBAAA.
\begin{equation*}
\begin{aligned} \text{Maximize} \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 5 x_1 + 5 x_2 \amp \leq 51, \\ \amp\amp 8 x_1 + 4x_3 \amp \leq 65, \\ \amp\amp x_2 \amp \geq 1, \\ \amp\amp x_1 \amp \leq 0, \\ \amp \amp x_3 \amp \leq 15, \\ \amp \amp x_2 \amp \leq 1, \\ \text{and} \amp\amp x_1, x_2, x_3 \amp \in \mathbb{N}_{0}.
\end{aligned}
\end{equation*}
This has the simplex tableau of
\begin{equation*}
\left[\begin{array}{rrr|rrrrrrrr|r} 1 \amp 7 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 53\\ 5 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 51\\ 8 \amp 0 \amp 4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 64\\ 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp -1\\ 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 15\\ 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1\\ \hline -3 \amp -6 \amp -5 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and applying the simplex method, we arrive at the following tableau:
\begin{equation*}
\begin{array}{r} 2 \mapsto 7, \\ 1 \mapsto 8, \\ 3 \mapsto 9, \\ 7 \mapsto 10, \end{array} \qquad \left[\begin{array}{rrr|rrrrrrrr|r} 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp -1 \amp -3 \amp -7 \amp 0 \amp 1\\ 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp -5 \amp 0 \amp -5 \amp 0 \amp 46\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp -8 \amp -4 \amp 0 \amp 0 \amp 4\\ 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1\\ 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 15\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0\\ \hline 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 3 \amp 5 \amp 6 \amp 1 \amp 81\\ \end{array} \right]
\end{equation*}
The basic solution of this tableau is
\begin{equation*}
\boldsymbol{x} = \left[\begin{array}{rrr|rrrrrrr} 0 \amp 1 \amp 15 \amp 1 \amp 46 \amp 4 \amp 0 \amp 0 \amp 0 \amp 0 \end{array}\right]
\end{equation*}
which is an integer solution with an objective value of \(81\text{.}\) Let’s see where we stand with the following tree diagram.
