(751g) A Hybrid Framework for Solving Multistage Stochastic Programs Under Both Endogenous and Exogenous Uncertainties
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)  and generalized knapsack-problem based decomposition algorithm (GKDA) . 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)  and a modified Lagrangean decomposition (mLD) of the MSSP. Similar to the existing Lagrangean decomposition schemes , 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  and instances of the process network synthesis problem from  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.
- Goel, V. and I.E. Grossmann, A Class of stochastic programs with decision dependent uncertainty. Mathematical Programming, 2006. 108(2/3): p. 355-394.
- 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.
- 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.
- 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.
- Gupta, V., & Grossmann, I. E. (2014). A new decomposition algorithm for multistage stochastic programs with endogenous uncertainties. Computers & Chemical Engineering, 62, 62-79.
- 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.
- 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