An Adaptive Partition-Based Approach for Solving Two-Stage Stochastic Programs with Fixed Recourse
研究了一种自适应调整分区的方法来求解固定补偿两阶段随机规划问题，通过细化与合并分区快速收敛到最优解，在测试实例上优于基本Benders分解，与水平法等方法竞争力相当。
We study an adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse. A partition-based formulation is a relaxation of the original stochastic program, and we study a finitely converging algorithm in which the partition is adaptively adjusted until it yields an optimal solution. A solution guided refinement strategy is developed to refine the partition by exploiting the relaxation solution obtained from a partition. In addition to refinement, we show that in the case of stochastic linear programs, it is possible to merge some components in a partition, without weakening the corresponding relaxation bound, thus allowing the partition size to be kept small. We also show that for stochastic linear programs with simple recourse, there exists a small partition that yields an optimal solution. The size of this partition is independent of the number of scenarios used in the model. Our computational results show that the proposed adaptive partition-based approach converges very fast to a small partition for our test instances. In particular, on our test instances the proposed approach outperforms basic versions of Benders decomposition and is competitive with the state-of-art methods such as the level method for stochastic linear programs with fixed recourse.