Computational experience with an interior point cutting plane algorithm

John E. Mitchell

There has been a great deal of success in the last twenty years with the use of cutting plane algorithms to solve specialized integer programming problems. Generally, these algorithms work by solving a sequence of linear programming relaxations of the integer programming problem, and they use the simplex algorithm to solve the relaxations. In this paper, we describe experiments using a predictor-corrector interior point method to solve the relaxations. For some problems, the interior point code requires considerably less time than a simplex based cutting plane algorithm.

Math Sciences, Rensselaer Polytechnic Institute, Troy NY 12180. February 24, 1997