A SURROGATE CUTTING PLANE ALGORITHM FOR ALL-INTEGER PROGRAMMING

Integer programming (IP) models have wide application in such diverse areas as production planning, cargo loading, personnel scheduling, portfolio selection, and dozens of others. In this paper authors present an all-integer cutting plane technique called the surrogate cutting plane algorithm (SCPA), for solving the all-integer (otherwise linear) programming problem. They develop and solve a smaller surrogate problem based on the solution of the LP relaxation, and thereby speed convergence to the optimal solution of the original problem. They exhibit the operation of the SCPA on three small example problems, and discuss computational results on a set of standard test problems.