(599ae) A Comparison of Sampling Approaches Used in a Sequential Sampling Approach for Stochastic Programming Problems with Continuous Uncertain Parameters

The size of a multi-stage stochastic program grows exponentially with the number of scenarios, which increases quickly for uncertain parameters represented with continuous distributions.  Therefore, it is necessary to determine the minimum number of scenarios to reach a preset confidence in the solution to reduce the computational cost of solving stochastic programming with continuously distributed random variables. This talk presents a comparison of sampling approaches used in a sequential sampling procedure. ^[1] This procedure is used to determine an appropriate number of scenarios required to cover the overall uncertain space in a multi-stage stochastic optimization problem with uncertain parameters that can be represented by continuous distributions. In the procedure, the sampling approach is used to discretize the continuous probability distributions for different numbers of scenarios. The studied sampling approaches are as follows: Monte Carlo method which relies on the repeated random sampling; Stratified sampling which divides an overall population into subpopulations and samples each subpopulation independently; Low-discrepancy sequences which consist of a sequence of points with the property that each subsequence ( x₁ , . . ., x_N ) for all N points has a low discrepancy; Univariate dimemsion reduction method (UDR) which estimates a multivariate function with multiple univariate functions.^[2] The different sampling approaches are compared in term of the necessary number of scenarios required to reach the preset optimality gap estimator defined in ^[1].

For each number of scenarios (n), the optimality gap estimator is calculated as the difference between the optimum solution of the stochastic program with n scenarios and the candidate solution, which is the optimum solution of the stochastic program with 2n scenarios. The procedure terminates when the estimation of the optimality gap is sufficiently small. Otherwise, the number of scenarios is increased.

A multi-stage stochastic program of the biomass to commodity chemicals (BTTC) investment planning, i.e., ethylene production from biomass, is used as the case study. The uncertainty parameters are the availability of the raw materials and the demand for the product. The objective is to minimize the expected total cost, which includes the raw material cost, the capital cost, and the R&D expenditure. The problem was formulated in GAMS 23.5 and solved using BARON. Low-discrepancy sequences modeling approaches required smaller number of scenarios to achieve the preset solution accuracy.

References:

[1] G. Bayraksan, D. P. Morton. A sequential sampling procedure for stochastic programming. Operations Research. 59. 898-913. 2011.

[2] S. H. Lee, W. Chen. A comparative study of uncertainty propagation methods for black-box-type problems. Struct Multidisc Optim. 37. 239-253. 2009.