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

许多整数规划问题可以通过检查松弛序列来解决。可能的松弛包括线性规划问题和半定规划（SDP）问题。本课题研究了用内点法求解松弛问题的整数规划问题。这些方法的发展将使解决以前被认为难以解决或太大的问题成为可能。初步结果表明，与单纯形切割平面法相比，内点切割平面法能够解决一些更大的MAXCUT问题，并且使用内点和单纯形切割平面的组合方法可以比单独使用内点或单纯形切割平面算法解决线性排序问题快一个数量级。并且对于具有许多子句的特定实例，用于MAXSAT问题的SDP切割平面算法比其他方法要快得多。

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.