Gomory Cutting Plane Method Examples: Integer Programming
In the previous section, we used Gomory cutting plane method to solve an Integer programming problem. In this section, we provide another example to enhance your knowledge. Let's concentrate on the following example:
Example 2: Gomory Cutting Plane Method
Maximize z = x1 + 4x2
subject to
2x1 + 4x2 ≤ 7
5x1 + 3x2 ≤ 15
x1, x2 are integers ≥ 0
Solution.
First, solve the above problem by applying the simplex method (try it yourself).The final simplex table is presented below.
Final Simplex Table
| cj | 1 | 4 | 0 | 0 | ||
|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | Solution values b (=XB) |
| 4 | x2 | 1/2 | 1 | 1/4 | 0 | 7/4 (1 + 3/4) |
| 0 | x4 | 7/2 | 0 | -3/4 | 1 | 39/4 (9 + 3/4) |
| zj–cj | 1 | 0 | 1 | 0 |
Taking first row as the source row, the corresponding equation
is
1/2x1 + 1x2 + 1/4x3 + 0x4 = 1 + 3/4
1/2x1 + (1 + 0)x2 + (1 - 3/4)x3 = 1
+ 3/4
Gomory's constraint
- (1/2x1 - 3/4x3) ≤
-3/4
-1/2x1 + 3/4x3 + x5 = -3/4
Table
| cj | 1 | 4 | 0 | 0 | 0 | ||
|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | Solution values b (=XB) |
| 4 | x2 | 1/2 | 1 | 1/4 | 0 | 0 | 7/4 |
| 0 | x4 | 7/2 | 0 | -3/4 | 1 | 0 | 39/4 |
| 0 | x5 | -1/2 | 0 | 3/4 | 0 | 1 | - 3/4 |
| zj–cj | 1 | 0 | 1 | 0 | 0 |
Table
| cj | 1 | 4 | 0 | 0 | 0 | ||
|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | Solution values b (=XB) |
| 4 | x2 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | x4 | 0 | 0 | 9/2 | 1 | 7 | 9/2 (4+1/2) |
| 1 | x1 | 1 | 0 | -3/2 | 0 | -2 | 3/2 (1+1/2) |
| zj–cj | 0 | 0 | 5/2 | 0 | 2 |
Taking second row as the source row, the corresponding equation is:
0x1 + 0x2 + 9/2x3 + 1x4 + 7x5 = 4 + 1/2
or (4 + 1/2)x3 + (1 + 0)x4 + (7 + 0)x5 = 4 + 1/2
Gomory's constraint
-1/2x3 ≤ -1/2
-1/2x3 + x6 = -1/2
Table
| cj | 1 | 4 | 0 | 0 | 0 | 0 | ||
|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | x6 | Solution values b (=XB) |
| 4 | x2 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | x4 | 0 | 0 | 9/2 | 1 | 7 | 0 | 9/2 |
| 1 | x1 | 1 | 0 | -3/2 | 0 | -2 | 0 | 3/2 |
| 0 | x6 | 0 | 0 | -1/2 | 0 | 0 | 1 | -1/2 |
| zj–cj | 0 | 0 | 5/2 | 0 | 2 | 0 |
In the above table, there is a negative value under XB column; therefore, apply the dual simplex method.
Final Table: Gomory Cutting Plane Method
| cj | 1 | 4 | 0 | 0 | 0 | 0 | ||
|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | x6 | Solution values b (=XB) |
| 4 | x2 | 0 | 1 | 0 | 0 | 1 | 2 | 0 |
| 0 | x4 | 0 | 0 | 0 | 1 | 7 | 9 | 0 |
| 1 | x1 | 1 | 0 | 0 | 0 | -2 | -3 | 3 |
| 0 | x3 | 0 | 0 | 1 | 0 | 0 | -2 | 1 |
| zj–cj | 0 | 0 | 0 | 0 | 2 | 5 |
The optimal solution is
x1 = 3, x2 = 0
z = 3 + 4 X 0 = 3
