Using an Interior Point Cutting Plane Method to Solve Integer Programming Problems.

摘要

There were several accomplishments of this research, both theoretical and computational. In joint work with Todd, we presented a cutting plane primal projective interior point method which we applied to matching problems, with encouraging computational results. Primal projective methods require a method to update the dual; we showed how various dual updates are related to each other and we also derived a dual projective algorithm. We derived a polynomial-time shifted barrier warm start algorithm which can be used in a cutting plane method; we showed that the directions obtained are strongly related to the directions derived in the work with Todd; computational results showed that the algorithm can be useful in some situations. The grant partially supported a Ph.D. student, Brian Borchers, who received his degree in August, 1992. His thesis concerned the use of branch-and-bound methods and contained good computational results as well as interesting theoretical observations. One paper from this thesis describes how the primal-dual interior point method can be used efficiently in a branch-and-bound method for solving mixed integer linear programming problem. Another paper describes how branch and bound algorithms for nonlinear integer programming problems can be improved. Borchers and I also developed a primal-dual interior point cutting plane method for solving linear ordering problems; the computational results for this algorithm were very encouraging, with run times comparable to those required by a simplex based cutting plane algorithm.