| dc.description.abstract | Multi-stage stochastic programming (MSSP) is a widely used framework for modeling optimization problems under uncertainty in the process industry. As problem size increases, these models become increasingly difficult to solve. This challenge is amplified in MSSP problems with type 2 endogenous uncertainty, where the timing of uncertainty realization is decision-dependent. In this case, non-anticipativity constraints (NACs) must be conditionally imposed to ensure that decisions remain identical across indistinguishable scenarios. These constraints significantly increase computational complexity, motivating the development of alternative solution approaches.
This dissertation addresses these challenges through three main initiatives: (1) compiling a library of 13 MSSP problems with type 2 endogenous uncertainty and characterizing their structural features, (2) introducing a new heuristic, the AbsolutE Value (AEV) solution approach, and (3) extending the existing heuristic, the Generalized Knapsack-problem-based Decomposition Algorithm (GKDA), for broader applicability using this library.
First, we compile a publicly available library of 13 MSSP models with type 2 endogenous uncertainty to aid our research community in developing solution approaches. The library contains eleven Mixed-Integer Linear Programming (MILP) models and two Mixed-Integer Nonlinear Programming (MINLP) models collected from published papers, along with nomenclatures, formulations, instance data, and Pyomo models. All models and instance data are available on our GitHub (https://github.com/CremaschiLab). We characterize the 13 problems based on their features, such as variable types, uncertainty sources, and recourse types. We introduce a new classification of variable types: post-realization decision variables, at-realization decision variables, and differentiator variables. The first two are defined based on when decision variables are allowed to take different values across distinguishable scenarios after uncertainty realization. Differentiator variables are defined by which variables trigger that realization. Each problem includes at least one post- or at-realization decision variable and at least one differentiator variable. All problems involve at least one source of endogenous uncertainty, and two also include an exogenous source. Five problems have complete recourse, two problems have fixed recourse, and six models do not have either complete or fixed recourse. We add complete recourse for models that lack both complete and fixed recourse. Computational results show that computational time increases with instance size, with a higher proportion of NACs. The computational time in complete-recourse-added models is typically longer than in the original models. When solved to optimality, the original and complete-recourse-added models yield nearly identical objective function values, with differences remaining within the specified solver tolerance.
Second, we propose a new heuristic—the AbsolutE Value (AEV) solution approach—as an improvement over the existing AEEV approach. AEV is designed to overcome a key limitation of AEEV: its potential to fail in generating feasible solutions when the problem lacks complete or fixed recourse. AEV constructs deterministic sub-problems using the outcome of each scenario among a set of indistinguishable scenarios. After solving these sub-problems, it evaluates the decision candidates suggested by individual scenario outcomes at each decision stage. AEV then selects a feasible and promising candidate that is expected to yield a high-quality primal bound for the original MSSP model. This design allows AEV to reliably generate feasible solutions even when complete or fixed recourse is absent, as long as at least one candidate corresponds to an extreme scenario outcome, such as a worst-case realization. To facilitate practical use, we developed Python packages for both the AEV and AEEV frameworks. These packages, available on GitHub (https://github.com/CremaschiLab), automate the implementation of both frameworks. We conducted a computational study on 55 instances derived from 13 MSSP models in the library. AEV produced feasible solutions in all instances, whereas AEEV failed in 15 due to infeasibility. Among the 40 instances where both approaches succeeded, AEV achieved a lower average gap from the MSSP feasible bound (0.57%) compared to AEEV (3.34%). Although AEV was slower than AEEV, its computational speedup increased with instance size, exhibiting a similar scalability trend to AEEV. For the largest instances of each problem, AEV achieved a speedup of 10^0.9 to 10^3.8 times over the MSSP model, compared to 10^1.3 to 10^4.5.
Finally, we extend and reassess GKDA, a heuristic designed to address the computational intractability of MSSP problems. While our previous work evaluated GKDA on four specific problems, its broader applicability remains underexplored. To address this gap, we extend the assessment to nine additional published MSSP problems in the library. GKDA improves computational efficiency by decomposing the original model by time and scenario into sub-problems. As a result, it loses both temporal and scenario information from the original MSSP model, which may affect solution quality. To mitigate the loss of temporal information, GKDA employs tailored approaches based on the conditions of each problem. In this study, we extend these approaches to additional problems, clarify the conditions under which each is applicable, and standardize the procedures for selecting the appropriate approach. We also update the conditions under which temporal information cannot be incorporated or GKDA is no longer applicable. Computational results across 47 instances show that GKDA achieves a speedup of up to four orders of magnitude compared to solving the MSSP models. The solution quality, measured by the gap from the MSSP model's solution, ranged from -0.7 % to 31.5%, with an average gap of 9.2%. These findings highlight the trade-offs between computational speed and solution quality, offering practical guidance on the conditions under which GKDA is most effectively applied to MSSP problems. All model data, code implementations, and the Python-based GKDA framework (using Pyomo) are available on GitHub (https://github.com/CremaschiLab). | en_US |
