(433f) Bounding Approaches to Various Multistage Stochastic Programming Problems with Type II Endogenous Uncertainty

In discrete decision processes, such as planning and scheduling, uncertainties can be classified as exogenous or endogenous. Uncertainties are realized independent from the decisions for exogenous uncertainty, while decisions impact what is learned or realized regarding endogenous uncertainties. Endogenous uncertainty is further classified into Type I and Type II [1]. For Type I, decisions influence the distribution of probability. In contrast, for Type II, which we focus on in this contribution, the decisions influence the realization time of the uncertainties. Multistage stochastic programming (MSSP) is an approach to model optimization problems with Type II endogenous uncertainty. In MSSP, possible combinations of outcomes of the uncertain parameters are represented as scenarios, and to prevent the decisions from anticipating the unrealized future outcomes, non-anticipativity constraints (NACs) are introduced. However, the number of NACs grows exponentially in MSSP models as the number of scenarios increases, leading to computational intractability in real-world-sized problems [2]. The solution approaches for large-scale MSSPs with endogenous uncertainty rely on heuristic, approximation, and decomposition methods, such as the sample average approximation algorithm [3], the improved Lagrangian decomposition framework [4], and the rolling-horizon heuristic approach [5], to address the challenge.

This presentation compares four heuristic approaches we developed for bounding the solution of MSSP problems with endogenous uncertainty using metrics such as optimality gap and solution time. The first approach, the absolute expected value solution (AEEV) [6], provides a general primal-bounding framework that builds on the concepts of the expected value solution and the value of the stochastic solution from multistage stochastic programs. It yields a tight feasible bound, and implementable solution for problems with complete recourse. The second approach is the generalized Knapsack-problem-based Decomposition Algorithm (GKDA) [7], which obtains feasible solutions for large-scale MSSPs. The GKDA decomposes the original multi-period MSSP into a series of knapsack problems and solves these problems at appropriate decision points of the planning horizon. The third approach, Relaxed Knapsack-problem-based decomposition Algorithm (RKDA) [8], efficiently generates tight dual bounds for large-scale MSSPs for a special subset of problems, resource-constrained multiple projects scheduling with stochastic task success. The RKDA relaxes the resource constraints and embeds the non-anticipativity of planning decisions in its framework. The fourth approach presents a modified Lagrangian decomposition (mLD) [9] for obtaining a valid dual bound for MSSPs. By exploiting the structure of the MSSP, a tight dual problem is formulated, which reduces the total number of Lagrange multipliers.

We employed these four approaches to generate primal and dual bounds for 11 MSSP models with Type II endogenous uncertainty. The models were collected from the open literature in a library [10] and are available as Pyomo files on our group's Github [11]. The models were developed for the size problem [12], gas-field development problem [13,14], process network synthesis [15], open-pit mining scheduling [16], pharmaceutical clinical trial planning [5,17,18], R&D portfolio planning [3], offshore oil/gas infrastructure planning [4], vehicle routing problem [19], artificial lift infrastructure planning [20], new technology investment planning [21], and demand-side response planning [22].

For the size problem [12], the production cost is the endogenous uncertainty. The MSSP model determines the optimum production size to minimize the demand's expected cost. In the gas-field development problem [13,14], reserves’ size and initial deliverability are endogenous uncertainties. The model maximizes the expected net present value (ENPV), where ENPV is the objective with the decisions such as the number of wells and facilities. In the synthesis of process networks problem [15], the process yields are endogenous uncertainties. The model determines the optimum installation and operation to maximize the ENPV. Endogenous geological uncertainties are considered in the open-pit mining scheduling problem [16], and the MSSP model determines the optimal schedule for extracting a mineral deposit to maximize the net present value (NPV). The MSSP model for the pharmaceutical clinical trial planning problem determines the optimum selection of drugs to push through the clinical trial phases and their start times where the trial outcomes are endogenous uncertainties [5,17,18]. For an R&D portfolio planning problem [3], return level and resource requirements are endogenous uncertainties, and the model determines the optimal allocation of resources to a set of projects. The endogenous uncertainties stem from fiscal rules and field parameters for the offshore oil/gas infrastructure planning problem [4]. The MSSP model determines the optional installation and operation to maximize the total ENPV. For the vehicle routing problem [19], demand is the endogenous uncertainty, and the model determines the optimal schedule for visits and loading. For the artificial lift infrastructure planning problem [20], the production rate is the endogenous uncertainty, and the model selects the optimal artificial lift methods and their installation plan. For the new technology investment planning problem [21], yields are the endogenous uncertainty, and the objective is to determine the technology investment plan that yields the minimum expected total cost. For the demand-side response planning problem [22], consumer participation level is the endogenous uncertainty. The MSSP model generates optimal investment decisions in conventional line reinforcements and responses to maximize the expected net benefit.

We solved these 11 problems with the four bounding approaches. The results revealed that the primal bounding approach, GKDA, can generate solutions within a few percent of the optimum, with solution times up to five orders of magnitude faster than solving the original MSSP. This presentation will introduce the bounding approaches and the model library and assess the strengths and weaknesses of each approach in generating bounds for the models in the library.

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. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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
10. Zeng, Z., & Cremaschi, S. (2022). A library of models and solution approaches for multistage stochastic programs under type II endogenous uncertainty. 2020 AIChE Annual Meeting.
11. https://github.com/CremaschiLab
12. 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.
13. 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.
14. 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.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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.
20. 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.
21. 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.
22. 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.