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

一种求解大规模随机规划的自适应划分方法

基本信息

批准号：
1854960
负责人：
Yongjia Song
金额：
$ 8.49万
依托单位：
Clemson University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-09-01 至 2021-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1854960&HistoricalAwards=false
关键词：
Adaptive Partition based Approach Solving

项目摘要

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.

随机程序是解决不确定性下需要优化的问题的流行模型。随机程序很难解决，尤其是当不确定性表征依赖于大量场景时。因此，场景分解和场景缩减（聚类和聚合）技术都用于减少计算负担。后者要么以启发式方式执行，要么以不利用来自中间解决方案的信息的方式执行。该项目的目标是改进一个基于在求解过程中自适应地划分场景集的计算框架。如果成功，该技术可以集成到现有的算法和软件中。通过实现更快的计算，并且在某些情况下可以解决更大的问题实例，该项目有可能影响大量需要在不确定性下进行优化的应用程序。基于自适应分区的框架将提供一种机制，通过用自适应构造的场景分区替换整个场景集，来聚合来自场景子问题的信息。如果成功，这将导致一种算法方式来协调近似分布和优化之间的工作。该方法将在随机程序的背景下将最优（静态）场景还原技术和正则化剖切面方法与不精确预言相结合。开发的算法将解决两阶段和多阶段随机线性程序以及随机整数程序。