(751g) A Hybrid Framework for Solving Multistage Stochastic Programs Under Both Endogenous and Exogenous Uncertainties

Optimization problems with decision-dependent (endogenous) and decision-independent (exogenous) uncertainties [1] are commonly observed in process industry. Most optimization problems with both uncertainties, by nature, can be modeled as multi-period multi-stage stochastic programs (MSSPs), where possible future states of the system are modelled as scenarios by enumerating all possible outcomes of uncertain parameters. One approach to generating MSSP formulations is to construct a deterministic mathematical programming model for each scenario and to introduce non-anticipativity constraints (NACs) in the formulation to prevent current state decisions from anticipating unrealized future outcomes. Unfortunately, these formulations need to account for all possible scenarios at all decision stages, and the models grow rapidly and become computationally intractable for real world problems.

In this talk, we introduce a new framework for efficiently solving MSSPs under both endogenous and exogenous uncertainties. The framework generates primal bounds utilizing two heuristic approaches developed by our group, the absolute expected value solution approach (AEEV) [2] and generalized knapsack-problem based decomposition algorithm (GKDA) [3]. Both heuristics decompose the original multi-period MSSP into a series of small sub-problems and solve these problems at appropriate decision points of the planning horizon. Both AEEV and GKDA implicitly incorporate all NACs and yield tight primal bounds up to several orders of magnitude faster than solving the MSSP. The dual bounds are generated by a hybrid approach, which utilizes the relaxed generalized knapsack decomposition algorithm (RGKDA) [4] and a modified Lagrangean decomposition (mLD) of the MSSP. Similar to the existing Lagrangean decomposition schemes [5], mLD regards initial and conditional NACs as complicating constraints, however utilizes the special structure of the conditional NACs to formulate a tighter dual problem, which also eliminates half of the Lagrange multipliers. The feasible solutions and primal bounds obtained from AEEV and GKDA are used to calculate the first set of Lagrange multipliers as a warm start. The iterative loop of the framework directs the AEEV and GKDA for updating the primal bound using the solution of the Lagrangean problem and employs the best primal solution to update the Lagrange multipliers. The algorithm terminates when the optimality gap is below a pre-specified value or when the maximum number of iterations is reached.

We applied the new framework to solve instances of the clinical trial planning problem derived from [6] and instances of the process network synthesis problem from [7] with up to 16,384 scenarios. Our results revealed that the AEEV and GKDA provided tight feasible bounds and even the optimum solution for some problems at the first iteration, and generated these bounds several orders of magnitude faster than solving the original problem. For example, the solutions of AEEV are within 0.00%, 0.75%, 0.00%, 0.43% and 0.65% of the true solution for two-, three-, four-, five- and six-drug cases, and are within 0.06% of the optimum for ten-year time-period and two-process instance for the process network synthesis problem. The dual bounds generated by the framework at first iteration were 1.4%, 2.3%, 1.2%, 1.9%, and 2.3% of the optimum for the clinical trial planning cases, yielding optimality gaps within 3.1% at the first iteration. For the illustrative two-drug case with 613 variables and 1051 constraints, the framework converged to 0.00% optimality gap in 25 iterations.

References

1. Goel, V. and I.E. Grossmann, A Class of stochastic programs with decision dependent uncertainty. Mathematical Programming, 2006. 108(2/3): p. 355-394.
2. 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.
3. Zeng, Z., Christian, B., & Cremaschi, S. (2018). A generalized knapsack-problem based decomposition heuristic for solving multistage stochastic programs with endogenous and/or exogenous uncertainties. Industrial & Engineering Chemistry Research, 57(28), 9185-9199.
4. Zeng, Z., & Cremaschi, S. (2018). A Relaxed Knapsack-Problem Based Decomposition Heuristic for Large-Scale Multistage Stochastic Programs. In Computer Aided Chemical Engineering (Vol. 43, pp. 519-524). Elsevier.
5. Gupta, V., & Grossmann, I. E. (2014). A new decomposition algorithm for multistage stochastic programs with endogenous uncertainties. Computers & Chemical Engineering, 62, 62-79.
6. 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.
7. Tarhan, B., & Grossmann, I. E. (2008). A multistage stochastic programming approach with strategies for uncertainty reduction in the synthesis of process networks with uncertain yields. Computers & Chemical Engineering, 32(4), 766-788