Integer and Combinatorial Optimization: Intersection Cuts from Multiple Rows

该项目的中心目标是加快过去15年来最先进的整数规划革命的步伐。直到20世纪90年代初，整数规划，一个通用的工具，用于建模现实世界的情况下，其特点是缺乏凸性，光滑性，连续性，只能解决非常小的问题实例。在过去的15年里，部分由于新的凸化程序的成功适应，整数规划的范围已经大大扩展，今天它可以科普涉及数千个变量和约束的问题。该项目旨在开发新的和更有效的凸化技术，其形式为直接从单纯形表导出的改进的提升和投影切割，来自多行或多项析取的相交切割，通过迭代析取模块化获得的切割，按字典顺序生成的纯整数切割等。待开发的技术承诺产生不仅更深，而且更多样化和稳定的切割，从而收紧当前混合整数规划的线性松弛，并减小在该过程中生成的搜索树的大小。预计这将增加一个数量级的大小的实例可解决的有用的时间，从而扩展范围的可解决的问题，出现在供应链管理，工业调度和其他现实世界的环境中的新类型的混合整数规划。

The central objective of this project is to accelerate the pace of the revolution in the state-of-the-art of integer programming that took place over the last 15 years. Until the early 1990's, integer programming, a universal tool for modeling real-world situations characterized by the absence of convexity, smoothness, continuity, could only solve very small problem instances. Over the last 15 years, due partly to the successful adaptation of new convexification procedures, the reach of integer programming has been vastly extended so that today it can cope with problems involving thousands of variables and constraints. This project is aimed at developing new and more efficient convexification techniques in the form of improved lift-and-project cuts derived directly from the simplex tableau, intersection cuts from multiple rows or multiple term disjunctions, cuts obtained by iterative disjunctive modularization, pure integer cuts generated lexicographically, and others.The techniques to be developed promise to yield cuts that are not only deeper, but more diverse and stable, thereby tightening the linear relaxation of the mixed integer programs at hand, and reducing the size of the search tree generated in the process. This is expected to increase by an order of magnitude the size of the instances solvable in useful time and thereby to extend the sphere of solvable problems to new types of mixed integer programs that arise in supply chain management, industrial scheduling and other real-world environments.