(120c) A New Decomposition Framework for Solving Multi-Stage Stochastic Programs with Endogenous Uncertainty

Optimization problems with decision-dependent, i.e., endogenous, uncertainty [1] are commonly observed in process industry, e.g., project portfolio management or R&D pipeline management problems [2], investment and operational planning of gas field developments [3], synthesis of process networks with uncertain process yields [4], and biomass-to-commodity chemicals investment planning [5]. Most optimization problems with endogenous uncertainty, by nature, can be modeled as multi-period multi-stage stochastic programs (MSSP). Unfortunately, these stochastic programming formulations grow exponentially with the increases in the numbers of scenarios and periods, and quickly become computationally intractable for real-world sized problems. An excellent review of existing literature for solving multi-stage problems with endogenous uncertainty can be found in [6]. In general, the solution approaches for large-scale stochastic programs with endogenous uncertainty rely heuristic or approximation approaches, and it has been shown that moderate-size problems can be solved to optimality. For example, Colvin and Maravelias [7] proposed a branch and cut algorithms for solving the pharmaceutical R&D pipeline management problems. Colvin and Maravelias [7, 8] and Gupta and Grossmann [9] introduced several theoretical reduction properties with iterative schemes based on relaxation of non-anticipativity constraints. Recently, Gupta and Grossmann [10] developed a new Lagrangean decomposition algorithm by decomposing the problem into scenario sub-problems.

In this talk, we introduce a new framework for efficiently solving multi-stage stochastic programs with endogenous uncertain parameters. The framework builds upon our Knapsack-problem based decomposition approach (KDA) [11, 12], which decomposes the original multi-period multi-stage stochastic program into a series of Knapsack problems, and solves these problems at appropriate decision points of the planning horizon. Our computational results revealed that the KDA provides tight feasible bounds for the original problem, and generates these bounds several orders of magnitude faster than solving the original problem. For example, for the pharmaceutical R&D pipeline management problem, the solutions of KDA are within 0.65%, 0.99%, 1.87% and 1.88% of the true solution for two-, three-, five- and six-product three-clinical trial cases, respectively. The KDA yielded these optimality gaps in 0.001, 0.03, 0.36 and 1.82 CPU seconds, which are up to five orders of magnitude faster than solving the original multi-stage stochastic programs. The decomposition framework - Lagrangean KDA (LKDA) - introduced here, employs KDA with a modified Lagrangean decomposition. The algorithm starts by executing KDA, which quickly generates a feasible solution and a lower bound (LB, assuming minimization). This feasible solution is used to calculate the first set of Lagrange multipliers. The modified Lagrangean problems are generated by removing the initial and conditional NACs, and dualizing the initial NACs in the objective function; this decomposes the Lagrangean problem to individual scenario problems, which are solved efficiently. The solution of the Lagrangean problem yields an upper bound. Next, the KDA is directed using the solution of the Lagrangean problem, and a new iteration is stated. As the iterations progress, to tighten the upper bound, violated conditional NACs are dualized and gradually added to modified Lagrangean problems. The algorithm terminates when the optimality gap is below a pre-specified value or when the maximum number of iterations are reached.

We applied the LKDA to solve two multi-stage stochastic problems: (1) the artificial lift infrastructure-planning problem [13], and (2) the pharmaceutical clinical trial planning problem [2]. The results show that LKDA successfully reduced the optimality gap below 5% quickly.

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. Colvin, M. and C.T. Maravelias, A stochastic programming approach for clinical trial planning in new drug development. Computers & Chemical Engineering, 2008. 32(11): p. 2626-2642.
3. Goel, V. and I.E. Grossmann, A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Computers & Chemical Engineering, 2004. 28(8): p. 1409-1429.
4. Tarhan, B. and I.E. Grossmann, A multistage stochastic programming approach with strategies for uncertainty reduction in the synthesis of process networks with uncertain yields. Computers & Chemical Engineering, 2008. 32(4-5): p. 766-788.
5. Fahmi, I. and S. Cremaschi, A prototype simulation-based optimization approach to model feedstock development for chemical process industry. Chemical Engineering Research and Design, 2013. 91(8): p. 1499-1507.
6. Apap, R.M. and I.E. Grossmann, Models and Computational Strategies for Multistage Stochastic Programming under Endogenous and Exogenous Uncertainties. Computers & Chemical Engineering.
7. Colvin, M. and C.T. Maravelias, A branch and cut framework for multi-stage stochastic programming problems under endogenous uncertainty, in Computer Aided Chemical Engineering. 2009. p. 255-260.
8. Colvin, M. and C.T. Maravelias, Scheduling of testing tasks and resource planning in new product development using stochastic programming. Computers & Chemical Engineering, 2009. 33(5): p. 964-976.
9. Gupta, V. and I.E. Grossmann, Solution strategies for multistage stochastic programming with endogenous uncertainties. Computers and Chemical Engineering, 2011. 35(11): p. 2235-2247.
10. Gupta, V. and I.E. Grossmann, A new decomposition algorithm for multistage stochastic programs with endogenous uncertainties. Computers & Chemical Engineering, 2014. 62(0): p. 62-79.
11. Christian, B. and S. Cremaschi, Variants to a knapsack decomposition heuristic for solving R&D pipeline management problems. Computers & Chemical Engineering, 2017. 96: p. 18-32.
12. Christian, B. and S. Cremaschi, Heuristic solution approaches to the pharmaceutical R&D pipeline management problem. Computers & Chemical Engineering, 2015. 74: p. 34-47.
13. Zeng, Z. and S. Cremaschi, Artificial Lift Infrastructure Planning for Shale Gas Producing Horizontal Wells, in Foundations of Computer Aided Process Operations / Chemical Process Control. 2017: Tucson, Arizona.