Polyhedral and Graph Theoretic Methods in Mixed Integer and Combinatorial Optimization

这个项目使用线性代数和图论的工具来解决整数规划和组合优化的理论和计算方面。它的重点是所谓的提升和项目的方法，在九十年代开发，最近纳入国家的最先进的软件。提升和投影切割是从包含不等式组合的析取中产生的。调查的一个主题是如何同时优化的加权组合的不平等使用的析取切割，并选择乘数的monoidal加强所产生的切割。在同一方向的另一个主题提供了提高性能的Gomory切割混合整数线性规划，通过结合不平等的定义明确的方式。 其他主题，旨在了解结构的雷曼矩阵和几乎完全unimodular矩阵，或算法，找到一个奇怪的洞在一个图，涉及到两个重要的问题：集包装和集覆盖。更好地理解这类问题是当前组合优化领域非常活跃的研究的一个核心方面。在某种程度上，该项目将取得成功，它将推进混合整数和组合优化领域的最新技术，从而提高我们在从工业生产到物流和电信的广泛活动中解决问题的能力。这里创建的工具可能在改善国土安全方面同样有用，因为它们可能有助于加强我们的技术领导地位。 从50年代末到90年代初，整数规划是一种几乎可以公式化任何优化问题的方法，但可用的计算机代码只能处理极小尺寸的玩具问题。在过去的十年中，艺术的状态发生了根本性的变化，今天超过一半的整数规划也可以解决。预计该项目将大大加速这一变化。

This project addresses theoretical and computational aspects of integer programming and combinatorial optimization, using the tools of linear algebra and graph theory. It is focused on the approach called lift-and-project, developed in the nineties and recently incorporated into state-of-the-art software. Lift-and-project cuts are generated from a disjunction involving a combination of inequalities. One topic for investigation is how to simultaneously optimize the weighted combination of inequalities used in the disjunction underlying the cut, and the choice of multipliers in the monoidal strengthening of the resulting cut. Another topic in the same direction offers to improve the performance of Gomory cuts for mixed integer linear programs, by combining inequalities in well-defined ways. Other topics, aimed at understanding the structure of Lehman matrices and almost totally unimodular matrices, or an algorithm for finding an odd hole in a graph, are related to two important classes of problems: set packing and set covering. A better understanding of these classes of problems is a central aspect of the very active research currently occurring in the field of combinatorial optimization.To the extent that this project will be successful, it will advance the state of the art in mixed integer and combinatorial optimization, and thereby enhance our problem solving ability in a broad range of activities, from industrial production to logistics and telecommunications. The tools created here may be as useful in improving homeland security, as they may be instrumental in reinforcing our technological leadership. From the late fifties to the early nineties, integer programming was a way to formulate almost any optimization problem, yet the available computer codes could only handle toy problems of minuscule size. During the last decade the state of the art has radically changed, and today well over half of the integer programs formulated can also be solved. This project is expected to significantly accelerate this change.