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.