Cutting Plane Method

In the previous section, we provided steps of the Gomory Cutting Plane Method. Now we will use that in solving Integer Programming problems.

Example 1: Cutting Plane Method

Maximize z = x₁ + 2x₂

subject to
2x₂ ≤ 7
x₁ + x₂ ≤ 7
2x₁ ≤ 11

x₁, x₂ are integers ≥ 0

Solution.

First, solve the above problem by applying the simplex method.

After introducing slack variables, the standard form of linear programming problem becomes

Maximize z = x₁ + 2x₂ + 0x₃ + 0x₄ + 0x5

subject to
2x₁ + x₃ = 7
x₁ + x₂ + x₄ = 7
2x₁ + x₅ = 11

Initial basic feasible solution

x₁ = 0, x₂ = 0, and z = 0
x₃ = 7, x₄ = 7, x₅ = 11

Table 1

Use Horizontal Scrollbar to View Full Table Calculation.

Key column = x₂ column
Minimum (7/2, 7/1) = 7/2
Key row = x₃ row
Pivot element = 2
x₃ departs & x₂ enters.

Table 2

x₄ departs and x₁ enters.

Table 3

On small screens, scroll horizontally to view full calculation

This solution is not acceptable since all the basic variables must be integer valued. Thus, we construct a Gomory's fractional cut to get the desired optimal solution.

Choose the largest fractional part under the X_B column. Here both the fractional parts are same. So either of the two may be used to develop Gomory's constraint.

Taking first row as the source row, the corresponding equation is
0x₁ + 1x₂ + 1/2x₃ + 0x₄ + 0x₅ = 3 + 1/2
(1 + 0)x₂ + 1/2x₃ = 3 + 1/2

After applying the formula we get

- 1/2 x₃ ≤ -1/2
- 1/2 x₃ + x₆ = - 1/2

x₆ is a slack variable

By adding the above equation in Table 3, we get the new table

Table 4

In the above table, there is a negative value under X_B column; therefore, apply the dual simplex method.
Select the most negative value from X_B column, i.e., -1/2
Therefore, key row = x₆ row
Key Column:

Key column = x₃ column
x₆ departs & x₃ enters

Final Table: Cutting Plane Method

The optimal solution is
x₁ = 4, x₂ = 3
z = 4 + 2 X 3 = 10