This section deals with the geometric representation of an integer programming problem.

To illustrate the concept of cutting plane method through **graphical method**, consider again the following problem.

Maximize z = x_{1} + 4x_{2}

subject to

2x_{1} + 4x_{2} ≤ 7

5x_{1} + 3x_{2} ≤ 15

x_{1}, x_{2} are integers ≥
0

Solution.

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

After introducing slack variables, we have

2x_{1} + 4x_{2} + x_{3} = 7

or x_{3} = 7 - 2x_{1} - 4x_{2} ....(i)

5x_{1} + 3x_{2} + x_{4} = 15

or x_{4} = 15 - 5x_{1} - 3x_{2} ....(ii)

Gomory's constraint

- (1/2x_{1} - 3/4 x_{3}) ≤
-3/4 ...(iii)

Substituting the value of x_{3} in equation (iii).

- 1/2x_{1} + 3/4 (7 -2x_{1} - 4x_{2}) ≤
-3/4

-2x_{1} - 3x_{2} ≤ -6
....(iv)

Gomory's constraint

-1/2x_{3} ≤ -1/2 ....(v)

Substituting the value of x_{3} in equation (v)

-1/2 (7 - 2x_{1} - 4x_{2}) ≤
-1/2

x_{1} + 2x_{2} ≤ 3 ....(vi)

The inclusion of two cuts( -2x_{1} - 3x_{2} ≤
-6, x_{1} + 2x_{2} ≤
3) give the new corner point A where x_{1} = 3, x_{2} = 0 and z = 3