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

多面体和非多面体剖切面方法：理论、算法和应用

• 批准号: 0317323
• 负责人: John Mitchell
• 金额: $ 22.49万
• 依托单位: Rensselaer Polytechnic Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0317323&HistoricalAwards=false
• 关键词: Polyhedral; Non; polyhedral; Cutting; Plane

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.

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