Polyhedral Combinatorics and Algorithms for Stochastic Integer Programming

点击翻译按钮获取中文摘要

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.