Accession Number:

ADA256041

Title:

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

Descriptive Note:

Final rept.

Corporate Author:

RENSSELAER POLYTECHNIC INST TROY NY DEPT OF MATHEMATICAL SCIENCES

Personal Author(s):

Report Date:

1992-09-30

Pagination or Media Count:

14.0

Abstract:

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE