(66b) Bounds for Multistage Stochastic Programs Under Endogenous Uncertainties

Multistage stochastic programming (MSSP) is an approach for modeling and solving optimization problems under uncertainty. Such problems are commonly seen in production planning and scheduling in chemical process industry. In MSSP, the total number of scenarios are the Cartesian product of all possible outcomes of uncertainties. A deterministic mathematical program can be constructed for each scenario, and decision variables are defined independently for each scenario in these problems. Then, non-anticipativity constraints (NACs) are added to link these scenario models to prevent decision variable values from anticipating unrealized future outcomes. Unfortunately, the MSSP formulations grow quickly and become computationally intractable for real-world size problems due to their space and time complexities.

To measure the expected loss when using a deterministic model (i.e., ignoring uncertainty) instead of its stochastic counterpart, Birge and Louveaux [1] introduced the value of the stochastic solution (VSS) concept for two-stage stochastic programming models with complete recourse. The VSS is calculated by taking the difference between the solution of the stochastic model (SRP) and the expected value solution of the deterministic problem (EEV). A large VSS indicates that it is crucial to obtain the solution of the stochastic program, while a small VSS means that it may be acceptable to obtain a deterministic solution using expected values of random variables and to avoid the computational time associated with solving the stochastic model. The concept of VSS has been recently extended to MSSPs with exogenous uncertainty, and different definitions of EEV were used to generate primal bounds for these problems [2].

This work extends the concepts of VSS and EEV to MSSPs with endogenous uncertainty and utilizes these concepts to introduce a general primal-bounding framework for MSSPs under endogenous and/or exogenous uncertainties with complete recourse. Unlike MSSP models under exogenous uncertainties, where the scenario structure is known in advance, observation of uncertainties and scenario structure in MSSPs with endogenous uncertainties are dependent on decisions made in previous stages. The MSSP models we consider may have continuous and/or discrete state variables. The proposed framework follows the nature of decision-making when planning in multiple decision stages under uncertainty, which is:

(decision¹ → observation¹â†’recourse¹)→(decision² → observation²â†’recourse²) →⋯→ (decisionⁿ→ observationⁿ→recourseⁿ),

where here-and-now decisions are made based on current available information and future unrevealed information is assumed based on expected results. After the here-and-now decisions are made, uncertainties are observed based on those decisions, and recourse actions are taken. In the planning horizon, decision makers repeat such decision processes until the end of planning horizon. The framework utilizes already known information and take the expected results for unrealized information to determine current state decisions, and then realize new uncertainty, and repeat this process along the planning horizon. A series of deterministic problems are generated and solved along the planning horizon and both endogenous and exogenous uncertainties are realized. The framework yields a tight feasible bound and an implementable solution for MSSPs under endogenous uncertainties, which we call the absolute expected value solution (AEEV) [3].

We compare different approaches for generating feasible solutions for MSSPs under endogenous and/or exogenous uncertainties using the VSS and EEV concepts and compare the strengths of the primal bounds obtained by these approaches using our framework. The absolute expected value of reference scenario (AEVRS) is developed based on the multistage expected value of the reference scenario, using the same structure of AEEV. The expected value solution EEV^t (t=1...T-1) is also introduced by solution of the stochastic model, where the decision variables are fixed using average scenario solution until stage t. We also introduce a Multistage Loss Using the Skeleton Solution until stage t, MLUSS^t, for MSSP under endogenous uncertainties, which is obtained by assigning a value of zero to stage variable whose values were equal to zero in the solution of the expected value model until stage t.

We apply AEEV, AEVRS, EEV^t, and MLUSS^t to process network synthesis problem from [4] under both uncertain process yields and uncertain product demand, and clinical trial planning problem from [5] with uncertain clinical trial outcomes. We solve two instances of the process networks synthesis problem with different planning-horizon lengths. The first case is a two time-period 3-stage problem. The second case is a ten time-period 9-stage problem. The clinical trial planning problems has different number of candidate drugs (i.e., 3-, 4-, 5-, 6-, and 7-drugs), and the MSSP model for the 7-drug case includes 16,384 scenarios. The computational results reveal that the AEEV and AEVRS provides tight feasible, and for come cases even optimal, solutions for these problems.

References

1. Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. Springer Science & Business Media.
2. Maggioni, F., Allevi, E., & Bertocchi, M. (2014). Bounds in multistage linear stochastic programming. Journal of Optimization Theory and Applications, 163(1), 200-229.
3. Zeng, Z., & Cremaschi, S. (2019). A general primal bounding framework for large-scale multistage stochastic programs under endogenous uncertainties. Chemical Engineering Research & Design: Transactions of the Institution of Chemical Engineers Part A, 141.
4. Goel, V., Grossmann, I. E. (2006). A class of stochastic programs with decision dependent uncertainty. Mathematical programming, 108(2), 355-394
5. Colvin, M., & Maravelias, C. T. (2008). A stochastic programming approach for clinical trial planning in new drug development. Computers & Chemical Engineering, 32(11), 2626-2642.