(189ab) An Efficient Approach to Bounding Multistage Stochastic Programs Using Sample Average Approximation

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