Integer Programming

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.

In this method, convergence is guaranteed in a finite number of iterations.

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

Steps

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
   - S f_ix_j £ -f_I
   - S 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.

   "The difficulty in life is the choice." - George Moore

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.