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.