Integer and Combinatorial Optimization: Polyhedral and Graph Theoretic Methods

整数和组合优化：多面体和图论方法

• 批准号: 0098427
• 负责人: Egon Balas
• 金额: $ 53.09万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-01 至 2004-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0098427&HistoricalAwards=false
• 关键词: Integer; Combinatorial; Optimization; Polyhedral; Graph

This project addresses basic theoretical and computational aspects of integer programming and combinatorial optimization, using tools of linear algebra and graph theory. In the nineties the principal investigators have developed a computationally successful approach to mixed 0-1 programming known as lift-and-project. A central theme of the research is to develop this approach in new directions that seem computationally even more promising. One of these directions uses a one to one correspondence recently established by the investigators' team between basic solutions to the higher dimensional linear program used to generate lift-and-project cuts, and certain basic solutions of the LP relaxation of the mixed integer program itself. This correspondence can be used to generate "deepest cuts" in the lift-and-project sense without explicitly generating the higher dimensional linear program. Another important topic is the creation of bridges from integer programming to the branch of computer science known as constraint programming. A recently discovered linear characterization of cardinality rules and similar logical constructs, along with the linear time separability of the inequalities involved, makes it possible to develop symbolic constraints usable in an integer programming context that may significantly enhance the power of algorithms dealing with problems involving logical conditions. A third line of research pursued under this project investigates properties of a 0-1 matrix that make the set packing problem or the set covering problem (or both) defined by it have only integer basic solutions. Structural properties of balanced matrices were obtained under previous NSF grants.; ideal and perfect matrices are currently under investigation.Decision makers often face problems that have a combinatorial aspect: choose one among a very large number of possible decisions. A standard approach is to formulate such problems as integer programs and to use a "solver" to find the best solution. Although integer programming solvers have improved significantly over the last decade, they are still unable to solve many large scale problems to optimality. This project lays the theoretical and analytical foundation for a new generation of solvers for integer programs. The lift-and-project approach developed by the principal investigators has proved well suited to solve hard integer programming problems. Speed remains an issue however. This research project addresses the speed issue by investigating new, faster ways of computing the cuts, lift-and-project as well as other. The potential benefits of the project are significant since cut generators are already being implemented in commercial integer programming solvers and, obviously, the performance of these solvers would be improved by better cut generators. Based on the recent increase in the use of solvers by managers in most fields of business, solvers with improved performance have the potential to increase productivity in the industries where these solvers are used (manufacturing, airline, financial and other industries).

这个项目使用线性代数和图论的工具，解决整数规划和组合优化的基本理论和计算方面。在90年代，主要研究人员开发了一种成功的计算方法，用于混合0-1编程，称为提升和投影。 研究的一个中心主题是在新的方向上发展这种方法，这些方向在计算上似乎更有前途。 其中一个方向使用了一个一对一的对应关系，最近建立的调查小组之间的基本解决方案，以高维线性规划用于产生提升和投影削减，和某些基本解决方案的LP松弛的混合整数规划本身。这种对应关系可以用来产生“最深切割”的提升和投影的意义，而不显式地产生更高的维度的线性规划。 另一个重要的主题是建立从整数规划到计算机科学的分支约束规划的桥梁。 最近发现的基数规则和类似的逻辑结构的线性表征，沿着与线性时间可分性的不等式，使得有可能开发符号约束，可用于整数规划的上下文中，可能会显着提高功率的算法处理涉及逻辑条件的问题。 在这个项目下进行的第三条研究线调查0-1矩阵的属性，使它定义的集合包装问题或集合覆盖问题（或两者）只有整数基本解决方案。 平衡矩阵的结构特性是在以前的NSF赠款下获得的。理想和完美的矩阵目前正在研究中。2决策者经常面临具有组合方面的问题：从大量可能的决策中选择一个。一个标准的方法是将这些问题公式化为整数规划，并使用“求解器”来找到最佳解决方案。 虽然整数规划求解器在过去的十年中有了显着的改进，但它们仍然无法解决许多大规模问题的最优性。 该项目为新一代整数规划求解器奠定了理论和分析基础。 由主要研究人员开发的提升和投影方法已被证明非常适合解决硬整数规划问题。然而，速度仍然是一个问题。 这个研究项目通过调查新的、更快的计算切割、提升和投影以及其他的方法来解决速度问题。 该项目的潜在好处是显着的，因为削减发电机已经在商业整数规划求解器，显然，这些求解器的性能将得到改善，更好的削减发电机。 基于最近大多数业务领域的管理人员使用求解器的增加，具有改进性能的求解器有可能提高使用这些求解器的行业（制造业，航空公司，金融和其他行业）的生产力。