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.