Models and Solution Approaches for Large-scale Multistage Stochastic Programs with Endogenous or/and Exogenous Uncertainty

Abstract

This dissertation aims to develop both models and solution approaches of multistage stochastic programs (MSSP) with endogenous and/or exogenous uncertainty. My work first develops two discrete-time large-scale nonconvex mixed-integer nonlinear programs (MINLP) models to solve the artificial lift infrastructure-planning problem. The problem is determining: (a) which artificial lift method should be installed, (b) when exactly the artificial lift method should be installed, and uninstalled. The objective is to maximize the net present value (NPV). Using the unique structure of the nonlinear terms, we formulate two equivalent mixed-integer linear programs MILP. Sets of tightening inequalities are used to decrease the solution times for both MINLP and MILP up to two orders of magnitude. We develop the MSSP model of artificial lift infrastructure planning problems by incorporating endogenous uncertainty of production rate, where the objective is to maximize the expected net present value (ENPV). The improvement and difference between the ENPVs of the stochastic and deterministic solutions, i.e., the value of the stochastic solution, is $163,831, a 5% increase from the deterministic solution. Secondly, we propose two alternatives multi-stage stochastic programming formulations to determine the optimal clinical trial plan under uncertainty. Decisions of a clinical trial plan include which clinical trials to start and their start times. Its objective is to maximize the expected net present value of the entire clinical trial plan. The MSSP model grows quickly and becomes computationally intractable for real-world sized problems due to their space and time complexities with increases in the number of uncertain parameters or increases in the number of realizations for each uncertain parameter. To address the complexity of MSSPs, my work to date has investigated different solution approaches for solving large-scale MSSPs with endogenous and/or exogenous uncertainties. The first approach develops a generalized Knapsack-problem based Decomposition Algorithm (GKDA) built upon the KDA (Christian and Cremaschi, 2014) to efficiently obtain feasible solutions for large-scale MSSPs with endogenous and/or exogenous uncertainties. 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 GKDA is applied to obtain feasible solutions for four different planning problems, which include continuous and discrete decision variables, recourse action variables, and both exogenous and endogenous uncertainties. The second approach develops a general primal-bounding framework based on extending the concepts of expected value solution and the value of the stochastic solution from multistage stochastic programs under exogenous uncertainties. It yields a tight feasible bound, and an implementable solution for multistage stochastic programs under endogenous uncertainties called the absolute expected value solution (AEEV). The third approach presents a new Lagrangian relaxation for obtaining a valid dual bound for MSSPs under endogenous uncertainties. By exploiting the structure of the MSSP, a tight dual problem is formulated, which reduces the total number of Lagrange multipliers with a modified multiplier updating scheme. The new Lagrangian relaxation is applied to bound instances of artificial lift infrastructure planning problem under uncertain production rate and the clinical trial planning problem under uncertain clinical trial outcomes. The fourth approach presents a Relaxed Knapsack-problem based decomposition Algorithm (RKDA) to efficiently generate tight dual bounds for large-scale MSSPs of resource-constrained multiple projects scheduling with stochastic task success. Unlike Lagrangian relaxation regarding and relaxing NACs as complicating constraints, the RKDA relaxes the resource constraints and embedding non-anticipativity of planning decisions in its framework. We develop the decomposition frameworks utilizing both GKDA and Lagrangian decomposition algorithm. The frameworks decompose original MSSP to individual scenario subproblems and are applied to instances of clinical trial planning problems. The primal and dual bounds obtained from GKDA and Lagrangian decomposition are updated iteratively. We also explore different frameworks with dual and primal bounding approaches for solving the MILP of the random forest model, which has similar complicating constraints with two-stage stochastic programs.