Polyhedral Combinatorics and Algorithms for Stochastic Integer Programming

随机整数规划的多面体组合和算法

• 批准号: 0700868
• 负责人: Yongpei Guan
• 金额: $ 14.25万
• 依托单位: University of Oklahoma Norman Campus
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-08-15 至 2009-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0700868&HistoricalAwards=false
• 关键词: Polyhedral; Combinatorics; Algorithms; Stochastic; Integer

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.

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