Integer Programming

Cutting Plane Method

Example 1

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 LPP 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

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

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:

Min

z3 - c3 -------- a43

Min

1/2 ------- -1/2

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

Table 5

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