Multistage Stochastic Integer Programming: Approximate Solution Methods and Applications

多阶段随机规划（MSP）为不确定性条件下的序贯决策提供了一个建模框架。数学规划的大多数应用都假设确定性数据。然而，真实的世界问题几乎总是包括一些不确定的参数（例如，在投资组合优化问题中，不同资产的回报在投资时是高度不确定的）。传统上很难高精度地预测这种不确定性，但现在随着大量历史记录的存在和数据分析的进步，我们可以准确地对不确定性进行建模。利用现有数据的能力使得有可能将不确定性纳入数学模型，这就是随机规划的情况。此外，在许多应用中，规划视野具有多个决策阶段，并且不确定性随着时间逐渐显露。因此，MSP是一种可行的建模方法。**MSP在能源、金融和调度等领域有许多应用。然而，MSP模型是出了名的难以解决的一般，现有的解决方案往往无法解决现实生活中的大小问题。由于其应用潜力和最先进的解决方案的局限性，该计划旨在为MSP（特别是整数变量）做出基本的算法和理论贡献，并将其应用扩展到各个领域。该计划的主题1将侧重于开发方法，这些方法可以克服MSP问题中的建模和算法挑战，特别是涉及整数变量的问题，并且可以提供（可证明）良好的可行政策。该方法将主要基于使用（线性）决策规则的新方法。特别是，新的决策规则将开发整数变量的MSP模型。将分析所提出的方法的易处理性和所获得的解决方案的质量。结果将大大推进国家的最先进的随机规划。*该计划的主题2将探索MSP的各种应用，如手术室调度，电力系统和投资组合优化。新的MSP模型将提出在这些领域的某些重要问题，并在确定性和两阶段的随机规划模型，这些模型的价值将进行调查。研究结果将为决策者提供宝贵的规划、调度和业务工具。

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.