Integer and Combinatorial Optimization: Intersection Cuts from Multiple Rows

整数和组合优化：从多行进行交集切割

• 批准号: 1024554
• 负责人: Egon Balas
• 金额: $ 40.09万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1024554&HistoricalAwards=false
• 关键词: Integer; Combinatorial; Optimization; Intersection; Cuts

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.

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