Solution Approaches to Large Scale Multistage Stochastic Programs with Endogenous and Exogenous Uncertainty

Abstract

The focus of this dissertation is the investigation of approaches to address the computational challenges of solving multistage stochastic programs (MSSPs) with both endogenous and exogenous uncertainty. My work to date has considered two MSSP case study problems. The first problem is the pharmaceutical R&D pipeline management problem where the objective is to determine the clinical trial schedule which maximized expected net present value considering uncertainty in the outcome of each clinical trial. The second is a new technology evaluation problem where the objective is to determine an optimal investment strategy for new technology development given uncertainty in the cost of capacity expansion, yield, technology success, and product demand. The computational complexity of MSSPs increases as the size of the problem (i.e. number of uncertain parameters) increases. To address this complexity, this dissertation introduces three different approaches. In the first approach, the goal was to find a feasible solution for computationally intractable MSSPs. To accomplish this, two heuristic algorithms that generate feasible solutions for the pharmaceutical clinical trial planning problem were developed. The first heuristic solves a series of two-stage stochastic programs with shrinking planning horizon. The second one uses a knapsack problem based approach to select clinical trial investments. The knapsack problem-based heuristic was generalized to Expected Value Decomposition Algorithm (EVDA) and used to solve instances of the NTIP problem. The EVDA algorithm provided tight feasible bounds on the solution of the deterministic MSSP for the NTIP problem. In the second approach, the computational complexity of the MSSPs is addressed using a branch and bound algorithm to find the true MSSP solution. The algorithm pairs the knapsack problem based decomposition heuristic with either an upper bound generated and updated using progressive hedging or optimal scenario solutions (OSS) to solve the clinical trial planning problem. The results reveal that both approaches reduce the computational resources required for solving large instances of the pharmaceutical clinical trial planning problem. The branch and bound algorithm with the OSS yielded a solution with a relative gap of 8% for a 7 product clinical trial planning problem which had previously been too large to generate and solve. The solution time for both algorithms makes the developed branch-and-bound algorithm unattractive for small problems, however, it can be used for problems which are too large to be generated using currently available computational resources. The third approach to reduce the computational complexity of MSSPs is to reduce the number of constraints needed to ensure that the solution does not anticipate the outcome of the uncertain parameters. Often the MSSP is written where the scenarios included do not represent the full set of scenarios. As such, it can be difficult to solve the problem as the traditional approaches for constraint reduction do not necessarily apply. This dissertation introduces an algorithm for generating the minimum cardinality non-anticipativity constraint set for MSSPs where the scenario set is a subset of the full set of scenarios. The approach is generalizable for MSSPs with gradually or instantaneously realized, endogenous and exogenous uncertainty.