(280d) A Library of Models and Solution Approaches for Multistage Stochastic Programs Under Type II Endogenous Uncertainty

The optimization problems with uncertainties are typical in the chemical process industry, especially in operation and design. In general, there are two types of uncertainties: endogenous, where decisions impact the realization of uncertainties and exogenous, where the realization of uncertainties is independent of decisions. The endogenous uncertainties can further be classified as Type I endogenous uncertainty [1], where decisions influence the probability distributions, and Type II endogenous uncertainty, where decisions impact the realization time of uncertainties. Most optimization problems with discrete planning horizon under endogenous uncertainty, by nature, can be modeled as multi-period multistage stochastic programming (MSSP) formulations. The scenarios represent the possible combinations of outcomes of uncertain parameters. The non-anticipativity constraints are introduced to prevent the decisions anticipating the unrealized future outcomes. However, 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 [2].

In this talk, we present a library of MSSP models with type II endogenous uncertainty and provide comparative solution statistics that were obtained by using the appropriate state-of-the-art commercial solvers and by using a suite of our previously developed solution approaches that rely on decomposition techniques. The literature contains 12 MSSP models with type II endogenous uncertainty. In 1998, the first MSSP model under endogenous uncertainty was introduced by [3], where the production cost was the endogenous uncertain parameter, realized after production decisions are made. Goel and Grossmann [4] and Goel et al. [5] developed MSSPs model for gas-field development problem, where the size and initial deliverability of reserves are endogenous uncertainties realized immediately after the drilling decisions are made. Tarhan and Grossmann [6] developed an MSSP model for synthesis of process networks, where the process yields were the endogenous uncertainties, gradually realized after the process operating decisions are made. An open-pit mining scheduling problem with endogenous geological uncertainties was introduced by Boland [7]. Colvin and Maravelias [8,9,10] proposed a pharmaceutical clinical trial planning problem with clinical trial outcomes as endogenous uncertainties. Solak [11] developed an R&D portfolio planning problem with return level as endogenous uncertainties. Kristianto [12] developed a model to optimize the integration of product architecture modularity and supply chain network planning under the endogenous production yield. Gupta and Grossmann [13] developed a MSSP model for investment and operation planning of offshore oil and gas filed infrastructure considering fiscal rules and field parameters as endogenous uncertainties. Khaligh and MirHassani [14] studied a MSSP model of vehicle routing problem with endogenous demand uncertainties realized after the visit decisions are made. Zeng and Cremaschi [15] developed an artificial lift infrastructure planning problem with the production rate as endogenous uncertainty realized after the selection of artificial lift methods. Christian and Cremaschi [16] developed a MSSP model for new technology investment planning problem with yields as endogenous uncertainty. Giannelos et al [17] developed an optimization model for investment planning of demand-side response (DSR) schemes regarding the consumer participation level as endogenous uncertainty. We summarize and differentiate the decision variables of the above models as here-and-now decisions and recourse actions. Different scenario generations and reduction properties for MSSP programs are also summarized and discussed. For example, the uncertainty can be treated as purely exogenous for a certain time period for some models where scenario pairs can not be distinguishable [10]. We also discuss possible and general ways of incorporation of non-anticipativity constraints in each problem, such as using the differentiator sets to distinguish scenario pairs [2].

We solve vehicle routing, artificial lift infrastructure planning, pharmaceutical clinical trial planning, and synthesis of process networks problems with our developed solution approaches, expected value solution approach (AEEV) [18], generalized knapsack-problem based decomposition algorithm (GKDA) [19], the relaxed generalized knapsack decomposition algorithm (RGKDA) [20], and a modified Lagrangean decomposition (mLD) of the MSSP [21]. The computational results show that the developed solution approaches were able to obtain optimal solutions for cases in artificial lift infrastructure planning and pharmaceutical clinical trial planning problems, and provide strong primal bounds for the remaining problems in solution times that are up to five orders of magnitude faster than the state-of-the-art commmercial solvers.

References

1. Goel, V., & Grossmann, I. E. (2006). A class of stochastic programs with decision dependent uncertainty. Mathematical programming, 108(2-3), 355-394.
2. Apap, R.M. and Grossmann, I.E., Models and computational strategies for multistage stochastic programming under endogenous and exogenous uncertainties. Computers & Chemical Engineering, 103, 2017; pp.233-274.
3. Jonsbråten, T. W., Wets, R. J., & Woodruff, D. L. (1998). A class of stochastic programs withdecision dependent random elements. Annals of Operations Research, 82, 83-106.
4. Goel, V., & Grossmann, I. E. (2004). A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Computers & chemical engineering, 28(8), 1409-1429.
5. Goel, V., Grossmann, I. E., El-Bakry, A. S., & Mulkay, E. L. (2006). A novel branch and bound algorithm for optimal development of gas fields under uncertainty in reserves. Computers & chemical engineering, 30(6-7), 1076-1092.
6. 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.
7. Boland, N., Dumitrescu, I., & Froyland, G. (2008). A multistage stochastic programming approach to open pit mine production scheduling with uncertain geology. Optimization online, 1-33.
8. 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.
9. Colvin, M., & Maravelias, C. T. (2009). Scheduling of testing tasks and resource planning in new product development using stochastic programming. Computers & Chemical Engineering, 33(5), 964-976.
10. Colvin, M., & Maravelias, C. T. (2010). Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming. European Journal of Operational Research, 203, 205-215.
11. Solak, S., Clarke, J. P. B., Johnson, E. L., & Barnes, E. R. (2010). Optimization of R&D project portfolios under endogenous uncertainty. European Journal of Operational Research, 207(1), 420-433.
12. Kristianto, Y. (2014, March). A Multi-period Bi-level Stochastic Programming with Decision Dependent Uncertainty in Supply Chains. In International Symposium on Combinatorial Optimization (pp. 315-324). Springer, Cham.
13. Gupta, V., & Grossmann, I. E. (2014). Multistage stochastic programming approach for offshore oilfield infrastructure planning under production sharing agreements and endogenous uncertainties. Journal of Petroleum Science and Engineering, 124, 180-197.
14. Hooshmand Khaligh, F., & MirHassani, S. A. (2016). A mathematical model for vehicle routing problem under endogenous uncertainty. International Journal of Production Research, 54(2), 579-590.
15. Zeng, Z., & Cremaschi, S. (2017). Artificial lift infrastructure planning for shale gas producing horizontal wells. Proceedings of the FOCAPO/CPC, Tuscan, AZ, USA, 8-12.
16. Christian, B., & Cremaschi, S. (2018). A multistage stochastic programming formulation to evaluate feedstock/process development for the chemical process industry. Chemical Engineering Science, 187, 223-244..
17. Giannelos, S., Konstantelos, I., & Strbac, G. (2018). Option Value of Demand-Side Response Schemes Under Decision-Dependent Uncertainty. IEEE Transactions on Power Systems, 33(5), 5103-5113.
18. 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.
19. 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.
20. 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.
21. Zeng, Z., & Cremaschi, S. (2020). A new lagrangean relaxation approach for multistage stochastic programs under endogenous uncertainties. 30th European Symposium on Computer Aided Chemical Engineering, Volume 47