Semidefinite Programming and Interior Point Cutting Plane Approaches to Integer Programming Problems

点击翻译按钮获取中文摘要

Many integer programming problems can be solved by examining a sequence of relaxations. Possible relaxations include linear programming problems and semidefinite programming (SDP) problems. This project is concerned with solving integer programming problems by using interior point methods to solve the relaxations. The development of these methods will make it possible to solve problems that were previously considered intractable or too large. Preliminary results show that an interior point cutting plane method is able to solve some far larger MAXCUT problems than with a simplex cutting plane method, that using a combination of an interior point and simplex cutting plane methods can be an order of magnitude faster than using either just an interior or simplex cutting plane algorithm for linear ordering problems, and that an SDP cutting plane algorithm for MAXSAT problems is considerably faster than other methods for certain instances with many clauses.