Multistage Stochastic Integer Programming: Approximate Solution Methods and Applications

多阶段随机整数规划：近似解法及应用

• 批准号: RGPIN-2018-04984
• 负责人: Bodur, Merve
• 金额: $ 2.62万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=686724
• 关键词: Multistage; Stochastic; Integer; Programming; Approximate

Multistage stochastic programming (MSP) provides a modeling framework for sequential decision making under uncertainty. The majority of the application of mathematical programming assumes deterministic data. However, real world problems almost always include some uncertain parameters (e.g., in a portfolio optimization problem, the returns of different assets are highly uncertain at the time of investment). It has been traditionally difficult to predict such uncertainties with a high accuracy, but now with the existence of substantial historical records and advances in data analytics, we can accurately model uncertainty. The ability to exploit available data made it possible to incorporate uncertainty into mathematical models, which is the case in stochastic programming. Moreover, in many applications, the planning horizon has multiple decision stages and the uncertainty is revealed gradually over time. Therefore, MSP is a viable modeling approach. ******MSP has numerous applications in areas like energy, finance, and scheduling. However, MSP models are notoriously hard to solve in general, and existing solution approaches frequently fail to solve real-life size problems. Motivated by its application potential and limitations of the state-of-the-art solution methods, this program aims to make fundamental algorithmic and theoretical contributions to MSP (especially with integer variables), and extend its applications in a variety of areas.******Theme 1 of the program will focus on developing methods that can overcome modeling and algorithmic challenges in the class of MSP problems, especially the ones involving integer variables, and that can provide (provably) good feasible policies. The methodology will be mostly based on novel ways of using (linear) decision rules. In particular, new decision rules will be developed for MSP models with integer variables. The tractability of the proposed methods and the quality of the obtained solutions will be analyzed. The results will significantly advance the state-of-the-art in stochastic programming.******Theme 2 of the program will explore diverse applications of MSP such as operating room scheduling, power systems and portfolio optimization. Novel MSP models will be proposed for certain important problems in these areas, and the value of such models over deterministic and two-stage stochastic programming models will be investigated. The results will provide valuable planning, scheduling and operational tools for decision makers.

多阶段随机编程（MSP）为不确定性下的顺序决策提供了建模框架。数学编程的大部分应用都假定确定性数据。但是，现实世界中的问题几乎总是包含一些不确定的参数（例如，在投资组合优化问题中，不同资产的回报在投资时高度不确定）。传统上，很难以很高的精度预测这种不确定性，但是现在，由于存在大量的历史记录和数据分析的进步，我们可以准确地对不确定性进行建模。利用可用数据的能力使得将不确定性纳入数学模型是可能的，这在随机编程中就是这种情况。此外，在许多应用程序中，计划视野具有多个决策阶段，并且随着时间的推移逐渐揭示了不确定性。因此，MSP是一种可行的建模方法。 ****** MSP在能源，金融和日程安排等领域有许多应用。但是，众所周知，MSP模型通常很难解决，并且现有的解决方案方法经常无法解决现实生活中的问题。该计划旨在以其最先进的解决方案方法的应用潜在和局限性的限制，旨在对MSP（尤其是整数变量）对基本算法和理论贡献做出基本的算法和理论贡献，并将其应用于各个领域。** ** ** ** ****该计划的主题1将集中于开发可以在MSP问题类别中克服建模和算法挑战的方法，尤其是涉及整数变量的方法，这些方法可以提供（证明是）良好的可行策略。该方法将主要基于使用（线性）决策规则的新颖方法。特别是，将为具有整数变量的MSP模型制定新的决策规则。将分析提出的方法的易干性和所获得的溶液的质量。结果将大大推动随机编程中的最新时间。将针对这些领域的某些重要问题提出新颖的MSP模型，并将研究此类模型比确定性和两阶段随机编程模型的价值。结果将为决策者提供宝贵的计划，调度和操作工具。