Polyhedral and Non-polyhedral Cutting Plane Methods: Theory, Algorithims and Applications

切割平面方法可用于解决许多类型的优化问题，包括整数规划问题。这些方法形成了问题的松弛序列，并逐渐收紧松弛，以找到原始问题的解决方案。多面体切割平面的工作方法与线性规划松弛问题有关。内部点切割平面方法具有解决单纯形方法无法解决的问题的潜力，因为问题的大小或因为可以在内部点上生成优越的切割平面。计算经验表明，这些方法优于单纯形切割平面方法，并且将内点法和单纯形法结合起来尤其有用。非多面体切割平面的方法看松弛，如半定规划问题。在这个建议中感兴趣的方法包括通过求解一系列较小的半定规划来解决半定规划问题，以及通过添加非多面体切割平面来解决整数规划问题。非多面体方法提供了解决以前未解决的问题的可能性，并使用新的，可能更好的方法来解决以前解决的问题。本建议中讨论的方法的发展将使解决以前被认为难以解决的问题成为可能。所提出的研究将产生有效的、实用的算法，用于解决许多类型的整数规划问题的大型实例，以及其他优化问题。这些问题将来自不同的领域，包括工程、经济、金融和物理。该提案将支持博士生。根据这项建议进行的研究将被纳入RPI的整数规划和线性规划研究生课程。将收集和生成各种问题的测试集，这些问题将在网络上提供。本项目产生的计算机代码将尽可能以电子方式提供。

Cutting plane methods can be used to solve many classes of optimization problems, including integer programming problems. These methods form a sequence of relaxations of the problem and gradually tighten the relaxations in order to find a solution to the original problem. Polyhedral cutting plane methods work with linear programming relaxations of the problem of interest. Interior point cutting plane methods have the potential to solve problems that are not amenable to simplex methods, because of the size of the problem or because superior cutting planes may be generated at an interior point. Computational experience suggests that these methods can outperform simplex cutting plane methods, and that combining interior point and simplex methods can be especially useful. Nonpolyhedral cutting plane methods look at relaxations such as semidefinite programming problems. Methods of interest in this proposal include solving semidefinite programming problems by solving a sequence of smaller semidefinite programs, and solving integer programs through the addition of nonpolyhedral cutting planes. The non-polyhedral approaches offer the possibility of tackling problems that were previously unsolved, and of using a new, possibly better, approach to problems previously solved.The development of the methods discussed in this proposal will make it possible to solve problems that were previously considered intractable. The proposed research will result in efficient, practical algorithms for solving large instances of many classes of integer programming problems, as well as other optimization problems. These problems will be drawn from diverse fields, including engineering, economics, finance, and physics. A doctoral student will be supported by this proposal. Research developed as a result of the proposal will be incorporated into graduate courses in integer programming and linear programming at RPI. Test sets for various problems will be collected and generated, and these problems will be made available on the web. Computer code arising from this project will be made available electronically where possible.