Sparse Integer Programming

稀疏整数规划

• 批准号: 1562578
• 负责人: Santanu Dey
• 金额: $ 29.37万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-08-01 至 2020-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1562578&HistoricalAwards=false
• 关键词: Sparse; Integer; Programming

Mixed-integer linear programming is a mathematical optimization framework that allows modeling discrete optimization problems that arise in various fields of engineering and business, such as chemical engineering, finance, forestry, health care, power systems, and supply-chain design. Most mixed-integer programming formulations that appear in these different areas of application involve very sparse constraint matrices. Many areas of scientific computing and optimization have been very successful in harnessing the effect of such sparsity of input data to improve the efficacy of algorithms. However, the use of sparsity of input data is a very under-explored direction of research in the context of mixed-integer linear programming algorithms. This award supports fundamental research for advancement of mixed-integer linear programming solver techniques for instances with sparse constraint matrices. Any improvement of the solvers obtained could result in significant gains to a large number of different applications. This project will support and train one PhD student who will be involved with all aspects of the research and dissemination of the results.The goal of this research is to systematically investigate the mathematical implications of sparse data matrices and to use this as a starting point for development of new and improved algorithms for solving mixed-integer linear programs that exploit sparsity in a holistic fashion. If successful, this project will be able to uncover formal mathematical explanation for various empirically observed behavior of mixed-integer linear programs, such as: Why does selection of sparse cutting-planes for mixed-integer linear programs with sparse constraint matrix work well in many cases? Why does feasibility pump, an important primal heuristic, work much better on average for mixed-integer linear programs with sparse constraint matrices? Why does the proportion of integral vertices to the total number of vertices of the linear programming relaxation of binary mixed-integer linear programs increase on an average as the formulations become more sparse? Using such insights, the research project will explore various avenues of improving mixed-integer linear programming solvers in order to better exploit sparsity, such as a new paradigm for sparse cut selection, increasing sparsity by use of extended formulations and combining new and different types of heuristics targeted towards better performance on sparse mixed-integer programming instances.

混合整数线性规划是一个数学优化框架，允许建模离散优化问题出现在工程和商业的各个领域，如化学工程，金融，林业，医疗保健，电力系统和供应链设计。在这些不同的应用领域中出现的大多数混合整数规划公式都涉及到非常稀疏的约束矩阵。科学计算和优化的许多领域已经非常成功地利用了输入数据的这种稀疏性的影响来提高算法的效率。然而，在混合整数线性规划算法的背景下，使用输入数据的稀疏性是一个非常未被探索的研究方向。该奖项支持基于稀疏约束矩阵实例的混合整数线性规划求解器技术的基础研究。所获得的求解器的任何改进都可以为大量不同的应用程序带来显著的收益。该项目将支持和培训一名博士生，该博士生将参与研究和成果传播的各个方面。本研究的目标是系统地研究稀疏数据矩阵的数学含义，并以此为起点，开发新的和改进的算法，用于解决以整体方式利用稀疏性的混合整数线性规划。如果成功，该项目将能够揭示各种经验观察到的混合整数线性规划行为的正式数学解释，例如：为什么选择具有稀疏约束矩阵的混合整数线性规划的稀疏切割平面在许多情况下工作得很好？为什么可行性泵，一个重要的原始启发式方法，在具有稀疏约束矩阵的混合整数线性规划中平均工作得更好？为什么二进制混合整数线性规划的线性规划松弛的积分顶点占顶点总数的比例随着公式变得更稀疏而平均增加？利用这些见解，该研究项目将探索改进混合整数线性规划求解器的各种途径，以便更好地利用稀疏性，例如稀疏切割选择的新范例，通过使用扩展公式来增加稀疏性，并结合新的和不同类型的启发式方法，以提高稀疏混合整数规划实例的性能。