Polyhedral Combinatorics and Algorithms for Stochastic Integer Programming

该补助金为研究多面体组合学和随机整数规划（IP）算法提供资金。在过去的十年中，随机IP已经得到了广泛的关注，在文献中作为一个有效的工具，建模和解决实时决策问题的考虑不确定事件。同时，随机IP同时具有整数规划和随机线性规划的复杂性，这使得它具有很大的挑战性，以解决大规模问题。本研究的重点是研究一般随机IP的基本结构，并开发快速算法来解决大规模问题。研究工作包括：1）研究强有效的不等式，并开发有效的分支和切割算法的随机批量问题，2）探索多面体组合数学的一般随机IP，和3）确定属性，将导致快速多项式时间和近似算法的几个特殊类别的随机IP问题。还将大力开发整数规划和随机优化的教学模块。本科生和研究生，强调代表性不足的群体，将参与该项目。如果成功，这项研究的结果将导致随机IP的科学方法创新。多面体的研究将有助于改进商业软件的发展，为广泛的随机IP问题。结果也可以与分解算法和基于优化的算法相结合，以提高大规模实际问题的建模和计算能力。例子包括生产计划，制造维修大修劳动力调度，和设施的位置问题。研究成果将最终提供内容和方法，可以纳入研究生课程，并可以作为新课程开发的基础。

This grant provides funding to study polyhedral combinatorics and algorithms for stochastic integer programming (IP). During the last decade, stochastic IP has received broad attention in the literature as an efficient tool for modeling and solving real-time decision making problems with the consideration of uncertain events. Meanwhile, stochastic IP incorporates both the complexity of integer programming and stochastic linear programming, which makes it challenging to solve large-scale problems. This research focuses on studying fundamental structures of general stochastic IP and developing fast algorithms for the solution of large-scale problems. The research work consists of 1) studying strong valid inequalities and developing efficient branch-and-cut algorithms for stochastic lot-sizing problems, 2) exploring polyhedral combinatorics for general stochastic IP, and 3) identifying properties that would lead to fast polynomial time and approximation algorithms for several special classes of stochastic IP problems. Significant efforts will also be spent developing teaching modules for integer programming and stochastic optimization. Undergraduate and graduate students, emphasizing underrepresented groups, will participate in the project.If successful, the results of this research will lead to scientific methodology innovations for stochastic IP. Polyhedral studies will contribute to the development of improved commercial software for a wide range of stochastic IP problems. The results may also be combined with decomposition algorithms and optimization-based heuristics to improve modeling and computational capabilities on large-scale practical problems. Examples include production planning, manufacturing repair overhaul workforce scheduling, and facility location problems. The research outcomes will finally provide content and methodologies that can be incorporated into graduate level courses and can serve as the bases for development of new courses.