Multi-stage stochastic programming (MSSP) is a scenario-based approach for optimization under uncertainty (Birge & Louveaux, 2011). Unfortunately, MSSP formulations quickly become prohibitively large especially for real-world sized problems where there are large numbers of uncertain parameters or many realizations for each uncertain parameter. In such cases, even generating the formulation may be inhibited by available computing resources. The computational complexity of these large-scale problems is primarily attributed to the size of the decision variables and the number of constraints.
Figure 1 shows the general MSSP problem structure when explicit formulation is employed. The structure consists of a set of constraints replicated for each of the scenario sub-problems and blocks of constraints called Non-Anticipativity Constraints (NACs). The NACs relate the decision variables in scenario sub-problems to ensure that the future outcomes of the uncertain parameter(s) are not anticipated.
Figure 1 Structure of a multistage stochastic program
Naturally, the number of decision variables and the number of constraints are greatly impacted by number of scenarios. The standard approach for scenario generation utilizes the Cartesian product of the outcomes for each uncertain parameter (Apap and Grossmann, 2016). Thus, as the number of uncertain parameters increases the number of scenarios in the problem grows exponentially. One approach used to reduce the computational complexity of MSSPs is sample average approximation (SAA). In SAA, a subset of scenarios are randomly selected, and the corresponding MSSP, which will be referred as SA-MSSP here, is formulated and solved. The process is repeated for a pre-determined number of times, and the solutions are used to construct confidence intervals on the MSSP objective and its optimality gap. Shapiro (2003) describes the application of sample average approximation for solving MSSPs in detail.
One challenge with generating SA-MSSP formulations efficiently, especially when the problem has endogenous uncertain parameters, is the lack of full scenario set. Traditional NAC-reduction approaches (Goel and Grossmann, 2006) are only applicable for full scenario sets. Recent graph theory approaches have allowed for minimum span NAC sets to be generated for sets of scenarios which are subsets of the full-scenario set. The graph theory based algorithm, Sample Non-Anticipativity Constraint algorithm (SNAC), begins by projecting scenarios onto an integer lattice. Using knowledge of the type of uncertainty, the algorithm develops a set of realization trajectories. The realization trajectories are used to gradually group scenarios. As scenarios are grouped the algorithm uses minimum span tree to add non-anticipativity constraints resulting in the minimum span non-anticipativity constraint set.
This presentation investigates the effectiveness of using SAA to generate bounds on three instances of the pharmaceutical clinical trial planning problem originally presented by Colvin and Maravelias (2008). The first instance considers a two-product case where the products are required to complete two clinical trials resulting in a total of 9 scenarios. A two-product and three-product instance both with three clinical trials are also considered. There are 16 scenarios in the two-product instance and 64 scenarios in the three-product instance. Sample scenarios are randomly selected from the full scenario set, the corresponding SA-MSSP is generated and solved. We implemented the SNAC approach for NAC generation. Objective function values of the SA-MSSP problem are used to generate confidence intervals on the objective function value for the original MSSP. The sample average problem for the pharmaceutical clinical trial planning problem provides a partial solution to the full-space problem. For the pharmaceutical clinical trial planning problem, the solution of SA-MSSP becomes feasible for the original MSSP if the decision variables associated with scenario that were not in the sample are assumed to be equal to zero. Hence, we also calculate the corresponding objective function value for the original problem using these feasible solutions to generate a primal bound for the MSSP. To show the effect of the min span NAC set we compare the solution times of the sample average problem using the full NAC set and NAC set generated using the graph theory algorithm. In the three-product case we found that the mean SAA-MSSP objective function value was 1856 with a confidence interval of 450 when the same size was 10% of the full scenario set. The confidence interval was reduced to a value of 322 when the percent of the full scenario set was increased from 10% to 25%. In both SAA-MSSP problems the true solution to the problem were slightly outside the confidence interval at 1189. Results of this study also show that solution times for the cases where the minimum span non-anticipativity constraint set was used were 50% better than the cases where the full set of non-anticipativity constraints were used.
References
Apap, R. M., & Grossmann, I. E. (2016). Models and Computational Strategies for Multistage Stochastic Programming under Endogenous and Exogenous Uncertainties. Computers & Chemical Engineering. https://doi.org/http://dx.doi.org/10.1016/j.compchemeng.2016.11.011
Birge, J. R., & Louveaux, F. (2011). Introduction to Stochastic Programming. Springer New York. Retrieved from https://books.google.com/books?id=Vp0Bp8kjPxUC
Colvin, M., & Maravelias, C. T. (2008). A stochastic programming approach for clinical trial planning in new drug development. Computers & Chemical Engineering, 32, 2626–2642. https://doi.org/10.1016/j.compchemeng.2007.11.010
Goel, V., & Grossmann, I. E. (2006). A Class of Stochastic Programs with Decision Dependent Uncertainty. Mathematical Programming, 108(2), 355–394.
Shapiro, A. (2003). Inference of statistical bounds for multistage stochastic programming problems. Mathematical Methods of Operations Research, 58(1), 57–68. https://doi.org/10.1007/s001860300280
See more of this Group/Topical: Computing and Systems Technology Division