Gomory Cutting Plane Algorithm

Historically, the first method for solving I.P.P. was the cutting plane method. This method is for the pure integer programming model.

The procedure is, first, ignore the integer stipulations, and solve the problem as an ordinary LPP.

If the solution satisfies the integer restrictions, then an optimal solution for the original problem is found. Otherwise, at each iteration, additional constraints are added to the original problem. These constraints are added to reduce or cut the solution space in every successive iteration, ruling out the current fractional solution, while ensuring that no integer solution is excluded in the process. The method terminates as soon as an integer-valued is obtained.

To summarize the approach, a series of steps are stated below.

Steps: Gomory Cutting Plane Algorithm

1. Use the simplex method to find an optimal solution of the problem, ignoring the integer condition.

2. Examine the optimal solution. Terminate the iterations if all the basic variables have integer values. Otherwise, construct a Gomory's fractional cut from the row, which has the largest fractional part, and add it to the original set of constraints.
Gomory's constraint
- Σ f_ix_j ≤ -f_I
- Σ f_ix_j + S_I = -f_I
Where:
f_I - fractional part
S_I - slack variable

In case of a tie, you are at liberty to choose any one arbitrarily.

3. Now, find a new linear programming solution. If the solution thus obtained is integral valued, then this is the required optimal solution of the original I.P.P.; otherwise, return to step 2.