10.3 Gomory’s Cutting Plane Method 591
x 2 = 412 , andf= 3412. The truncation of the fractional part of this solution gives
x 1 = , 5 x 2 = , and 4 f=31. Although this truncated solution happened to be optimum
to the corresponding integer problem in the earlier case, it is not so in the present case.
In this case the optimum solution of the integer programming problem is given by
x 1 ∗= , 0 x 2 ∗= , and 8 f∗= 2. 3
10.3 Gomory’s Cutting Plane Method
10.3.1 Concept of a Cutting Plane
Gomory’s method is based on the idea of generating a cutting plane. To illustrate
the concept of a cutting plane, we again consider the problem stated in Eqs. (10.1).
The feasible region of the problem is denoted byABCD in Fig. 10.1. The optimal
solution of the problem, without considering the integer requirement, is given by point
C. This point corresponds tox 1 = 512 ,x 2 = 412 , and f= 3412 , which is not optimal to
the integer programming problem since the values ofx 1 andx 2 are not integers. The
feasible integer solutions of the problem are denoted by dots in Fig. 10.1. These points
are called theinteger lattice points.
In Fig. 10.3, the original feasible region is reduced to a new feasible region
ABEFGDby including the additional (arbitrarily selected) constraints. The idea behind
Figure 10.3 Effect of additional constraints.
