A surrogate cutting plane algorithm for all-integer programming (Q1086159)

We present an all-integer cutting plane technique called the surrogate cutting plane algorithm (SCPA), for solving the all-integer (otherwise linear) programming problem. We 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. We exhibit the operation of the SCPA on three small example problems, and discuss computational results on a set of standard test problems.