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) : Mitchell, John E


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a256041.pdf


Report Date : 30 Sep 1992


Pagination or Media Count : 14


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.


Descriptors :   *INTEGER PROGRAMMING , *PROBLEM SOLVING , *CUTTING , ALGORITHMS , STUDENTS , OBSERVATION , POLYNOMIALS , MATCHING , GRANTS , PAPER , BARRIERS , TIME , THESES , COMPUTER PROGRAMMING , LINEAR PROGRAMMING


Subject Categories : Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE