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

Clemson University, Clemson SC

Investigators

Abstract

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.