Integer and Combinatorial Optimization: Polyhedral and Graph Theoretic Methods

本项目利用线性代数和图论的工具，解决了整数规划和组合优化的基本理论和计算方面的问题。在九十年代，主要研究人员开发了一种计算上成功的混合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).