The initial objective function is to minimize x1 + x2 + x3 + x4, given the following constraints:
| 1 | 0 | 0 | 0 | >= | 21 |
| 0 | 1 | 0 | 0 | >= | 39 |
| 0 | 0 | 1 | 0 | >= | 61 |
| 0 | 0 | 0 | 1 | >= | 14 |
Objective value is 135. This is the dummy case where no cutting takes place. The dual solution is (1, 1, 1, 1), so the next LP to solve is: max p1 + p2 + p3 + p4 subject to 13*p1 + 31*p2 + 36*p3 + 45*p4 <= 100. The solution is (7, 0, 0, 0), and since the objective value of 7 is greater than 1, continue. Add this column in the next run. The pattern generated here (7, 0, 0, 0) means that 7 pieces of length 13 will be cut from the stock, whose length is 100.
Now with the addition of a new variable, minimize x1 + x2 + x3 + x4 + x5, given the following constraints:
| 1 | 0 | 0 | 0 | 7 | >= | 21 |
| 0 | 1 | 0 | 0 | 0 | >= | 39 |
| 0 | 0 | 1 | 0 | 0 | >= | 61 |
| 0 | 0 | 0 | 1 | 0 | >= | 14 |
The objective value has decreased to 117, and the dual solution is (1/7, 1, 1, 1), so the next LP to solve is: max 1/7*p1 + p2 + p3 + p4 subject to 13*p1 + 31*p2 + 36*p3 + 45*p4 <= 100. The constraint is the same as the earlier maximization problem. The solution is (0, 3, 0, 0), so this would be the next column to generate, given that the the objective value of 3 is still greater than 1. Continue this process.
