(400f) Characterization of Multistage Stochastic Programming Problems with Type II Endogenous Uncertainty to Develop Common Primal Bounding Approaches

There are many optimization problems where uncertainties depend on decisions and are sequentially realized over time in the chemical process industry [1,2,3,4]. Since these problems consider multiple scenarios and a time horizon divided discretely, multistage stochastic programming (MSSP) is one of the approaches to solve them. In stochastic programming, uncertainty has two classes, exogenous and endogenous. For exogenous uncertainty, uncertainties are realized independently of the decisions, while decisions impact outcomes of endogenous uncertainty. Endogenous uncertainty can be grouped into two sub-classes: type I, where the probability distribution is decision-dependent, and type II, where the realization time is decision-dependent [5]. In MSSP problems with type II endogenous uncertainty, which we focus on in this contribution, decisions gradually distinguish scenarios over time based on the outcomes. The constraints enforcing scenario indistinguishability are called non-anticipativity constraints (NACs). However, the increase in the number of scenarios causes exponential growth of NACs, making solving real-world-size problems intractable [6]. Hence, various approaches have been developed to circumvent the intractability, including the sample average approximation algorithm [7], the improved Lagrangian decomposition framework [3], and the rolling-horizon heuristic approach [8].

The two heuristic approaches, the absolute expected value solution (AEEV) [9] and the generalized knapsack-problem-based decomposition algorithm (GKDA) [10], which we have developed, generate primal bounds of MSSP problems with endogenous uncertainty without NACs and thereby with shorter computational time than solving the MSSP. AEEV generates deterministic sub-problems instead of an MSSP problem by decomposing scenarios of the MSSP formulation. AEEV iterates by solving sub-problems, fixing here-and-now decision variables, judging whether there are realizations, solving recourse action sub-problems based on the realized information, and fixing the recourse action variables along the planning horizon. GKDA generates knapsack sub-problems (KSPs) instead of an MSSP problem by decomposing scenarios and time periods of the MSSP formulation. First, GKDA lists all admissible decision variables as eligible items at each time period and computes each item value based on the conditions MSSP problems inherently have. Then, GKDA iteratively solves KSPs, fixes here-and-now decision variables, checks if there are realizations, solves recourse action KSPs based on the realized information, fixes the recourse action variables, and updates the eligible item list until the end of the planning horizon. One of the properties we expect from these two heuristic approaches is the universal applicability to any MSSP problems with type II endogenous uncertainty in addition to the computational speed and small optimality gap. However, the solutions of AEEV sub-problems or GKDA KSPs may be infeasible, depending on the original MSSP problem characteristics. In this study, we characterized MSSP problems with type II endogenous uncertainty to clarify the properties that cause inapplicability in AEEV and GKDA solutions by examining published MSSP problems with Type II endogenous uncertainty [1,2,3,4,7,8,11,12,13,14,15,16].

Our group sorted these MSSP problems based on their properties, such as the number of sources of uncertainties, ways of scenario generations, and the mathematical programming form [17]. These properties may affect the feasibility and quality of the solution generated by AEEV and GKDA. In this contribution, we focus on two properties of MSSP problems that affect the applicability of AEEV or GKDA. The first property is related to the type of recourse in the MSSPs. A stochastic program has relatively complete recourse if every solution to state decision variables is feasible and has a feasible completion with recourse action variables [18]. Although relatively complete recourse is useful, it may be difficult to identify because it requires problem-specific knowledge. Therefore, to ensure that no outcome produces infeasible results, complete recourse, a special type of relatively complete recourse, is often added to the models. The second property is the time lag between fixing state decision variables and their implementation. For example, an investment made for installing a reactor at a certain time becomes operational at a later time.

We examined the effect of the two properties by applying AEEV and GKDA to the MSSP problems. Recourse is essential in circumventing infeasible solutions in both AEEV and GKDA. Suppose an MSSP problem does not have relatively complete recourse. In that case, the sub-problems of AEEV or KSPs of GKDA may be infeasible because there is no guarantee for the feasibility of the subsequent sub-problems or KSPs. For example, the vehicle routing problem [14] determines the optimal order of visiting customers with uncertain demand. The vehicle visits the customers to satisfy their demands and refills at the depot between customer visits whenever necessary. The vehicle never visits a customer whose potential demand exceeds the vehicle's load. In other words, since the vehicle doesn't need to consider visiting another customer when it fails to supply demand, the MSSP problem doesn't have relatively complete recourse. On the other hand, AEEV and GKDA might select potential customers whose demand is beyond the vehicle's load because they determine the order of visits based on the expected-valued demand in deterministic sub-problems or KSPs, in which case the sub-problems or KSPs become infeasible.

The time lag between the decisions and implementation may cause infeasibility in GKDA. Since GKDA decomposes time indexes of the original MSSP problems, KSPs lack time indexes, causing a lack of forethought. Accordingly, GKDA considers only the objective function and never considers the weight constraints that influence later time, thereby generating infeasible solutions to KSPs. On the other hand, time lag does not cause infeasibility for AEEV because it decomposes only scenario indexes and retains time indexes. For example, the demand-side response planning problem [16] determines investment in reinforcements on the power network to prepare for increasing power demand. However, such reinforcements need time for completion. In this case, GKDA never selects corresponding items because they only incur the cost and are not beneficial when decisions are made, even if those are necessary investments in subsequent periods.

Our past studies showed that AEEV and GKDA yield solutions with optimality gaps of 0 to 1% and 0 to 10% with several orders of magnitude faster than solving MSSPs [9, 10] with relatively complete recourse and no time lag. Hence, our future work will focus on exploiting the two properties discussed to extend the applicability of AEEV and GKDA to problems that do not have relatively complete recourse.

References

1. Goel, V., & Grossmann, I. E. (2004). A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Comput. & Chem. Eng., 28(8), 1409-1429.
2. 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. Comput. & Chem. Eng., 32(4-5), 766-788.
3. Gupta, V., & Grossmann, I. E. (2014). Multistage stochastic programming approach for offshore oilfield infrastructure planning under production sharing agreements and endogenous uncertainties. J. Pet. Sci. Eng., 124, 180-197.
4. 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.
5. Goel, V., & Grossmann, I. E. (2006), A class of stochastic programs with decision dependent. uncertainty Math. Program., 108(2-3), 355-394.
6. Apap, R.M. and Grossmann, I.E. (2017), Models and computational strategies for multistage stochastic programming under endogenous and exogenous uncertainties. Comput. Chem.Eng., 103; 233-274
7. Solak, S., Clarke, J. P. B., Johnson, E. L., & Barnes, E. R. (2010), Optimization of R&D project portfolios under endogenous uncertainty. Eur. J. Oper. Res., 207(1), 420-433.
8. Colvin, M., & Maravelias, C. T. (2009), Scheduling of testing tasks and resource planning in new product development using stochastic programming. Comput. & Chem. Eng., 33(5), 964-976.
9. Zeng, Z., & Cremaschi, S. (2019), A general primal bounding framework for large-scale multistage stochastic programs under endogenous uncertainties. Chem. Eng. Res. Des.: 141, 464-480.
10. 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. Ind. Eng. Chem. Res., 57(28), 9185-9199.
11. https://github.com/CremaschiLab
12. Jonsbråten, T. W., Wets, R. J., & Woodruff, D. L. (1998). A class of stochastic programs with decision dependent random elements. Ann. Oper. Res., 82, 83-106.
13. 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.
14. Hooshmand Khaligh, F., & MirHassani, S. A. (2016), A mathematical model for vehicle routing problem under endogenous uncertainty. Int. J. Prod. Res., 54(2), 579-590.
15. Christian, B., & Cremaschi, S. (2018). A multistage stochastic programming formulation to evaluate feedstock/process development for the chemical process industry. Chem. Eng. Sci., 187, 223-244.
16. Giannelos, S., Konstantelos, I., & Strbac, G. (2018). Option Value of Demand-Side Response Schemes Under Decision-Dependent Uncertainty. IEEE Trans., 33(5), 5103-5113.
17. 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.
18. John R. Birge, François Louveaux (2011). Introduction to Stochastic Programming (2nd ed.). Springer Series in Operations Research and Financial Engineering