Integer and Combinatorial Optimization: Polyhedral and Graph Theoretic Methods

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

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).