Sequential Bounding Methods for Two-Stage Stochastic Programs
针对两阶段随机规划问题，提出新算法改进边界并减少近似误差，通过半导体库存管理实例与SAA算法对比，用t检验评估解的质量。
In rare situations, stochastic programs can be solved analytically. Otherwise, approximation is necessary to solve stochastic programs with a large or infinite number of scenarios to a desired level of accuracy. This involves statistical sampling or deterministic selection of a finite set of scenarios to obtain a tractable deterministic equivalent problem. Some of these approaches rely on bounds for primal and dual decision variables of the second stage. We develop new algorithms to improve these bounds and reduce the deterministic approximation error. Experiments were conducted to compare a sequential approximation approach with and without these new algorithms. Each algorithm is applied to a set of test instances for a problem of managing semiconductor inventory with downward substitutions, where random variables only appear in the right-hand side of the second stage. Experiments were also conducted using a sample average approximation (SAA) algorithm. The sequential approximation and SAA algorithm generate a feasible solution upon termination. We directly compare the quality of these solutions using a paired student t-test.