An Adaptive Partition-based Approach for Solving Large-Scale Stochastic Programs

随机规划是求解不确定条件下最优化问题的常用模型。求解随机程序具有挑战性，特别是当不确定性表征依赖于大量场景时。因此，使用场景分解和场景约简（聚类和聚合）技术来减少计算负担。后者要么以启发式方式执行，要么以不利用中间解决方案信息的方式执行。该项目的目标是在解决方案过程中，基于自适应地划分场景集来推进计算框架。如果成功，这项技术有可能集成到现有的算法和软件中。通过实现更快的计算，并在某些情况下使解决更大的问题实例成为可能，该项目有可能影响在不确定情况下需要优化的整个应用程序主机。基于自适应分区的框架将提供一种机制，通过将整个场景集替换为自适应构建的场景分区，从场景子问题中聚合信息。如果成功，这将导致一种算法方法来协调近似分布和优化之间的努力。该方法将最优（静态）场景约简技术和正则化切割平面方法与随机规划中的不精确预言相结合。所开发的算法将处理两阶段和多阶段随机线性规划以及随机整数规划。

Stochastic programs are popular models for problems requiring optimization under uncertainty. Stochastic programs are challenging to solve, especially when uncertainty characterization relies on a large number of scenarios. Consequently, both scenario decomposition and scenario reduction (clustering and aggregation) techniques are used to reduce computational burden. The latter are performed either in a heuristic manner, or in a way that does not utilize information from intermediate solutions. This project's objective is to advance a computational framework based on partitioning the scenario set adaptively during the solution process. If successful, the technique can be potentially integrated into existing algorithms and software. By enabling faster computation, and in some cases making it possible to solve larger problem instances, the project has the potential to impact a whole host of applications requiring optimization under uncertainty. The adaptive partition-based framework will provide a mechanism to aggregate information from scenario sub-problems, by replacing the entire scenario set with an adaptively constructed partition of scenarios. If successful, this will lead to an algorithmic way to coordinate the efforts between approximating the distribution and optimization. The approach will integrate both the optimal (static) scenario reduction technique and the regularized cutting-plane method with inexact oracles in the context of stochastic programs. The developed algorithms will address two-stage and multi-stage stochastic linear programs as well as stochastic integer programs.