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

- Conference: AIChE Annual Meeting
- Year: 2017
- Proceeding: 2017 AIChE Annual Meeting
- Group: Computing and Systems Technology Division
- Session:
- Time:
Monday, October 30, 2017 - 5:35pm-5:40pm

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

### Checkout

This paper has an Extended Abstract file available; you must purchase the conference proceedings to access it.

#### Do you already own this?

Log In for instructions on accessing this content.

### Pricing

####
**Individuals**

AIChE Members | $150.00 |

AIChE Graduate Student Members | Free |

AIChE Undergraduate Student Members | Free |

Non-Members | $225.00 |