(8x) Solution Approaches for Large Scale Multistage Stochastic Programs with Endogenous and Exogenous Uncertainty

Authors: 
Christian, B., University of Tulsa
Research Interests:

Multistage stochastic programs (MSSPs) with endogenous and exogenous uncertainty arise from problems where there is uncertainty in one or more of the problem parameters. In chemical engineering these problems can include the pharmaceutical clinical trial planning problem (Colvin and Maravelias, 2008), the oil field infrastructure planning problem (Gupta & Grossmann, 2011), and the process synthesis problem (Goel & Grossmann, 2006). Multistage stochastic programming formulations are limited computationally by problem size. The growth of the problem is related to the number of uncertain parameters and the number of realizations for each uncertain parameter. Linear increases in the number of uncertain parameters cause the number of scenarios in a MSSP to grow exponentially. Similarly, non-linear growth in problem size is also seen when the number of realizations for each uncertain parameter is increased. Increasing the number of scenarios in a MSSP increases the size of the decision variables and the number of constraints. As a result, most MSSPs considered in literature are limited to a few uncertain parameters with a few realizations for each parameter.

Often real-world size problems have many uncertain parameters with multiple realizations. Therefore, the MSSPs of these problems quickly become computationally intractable. One approach to addressing the computation complexity of MSSPs is to develop improvements for existing solution procedures. Sample Average Approximation (SAA) is a commonly applied approach to determine upper and lower bounds for a MSSPs. One challenge faced in generating the SAA form of the problem is the generation of the constraints. During my PhD I have been able to use my of graph theory to develop a systematic approach to generate constraints for the SAA problem.

One drawback to the SAA approach is that the approach can only provide bounds on the true solution. In my graduate studies, I have worked on the development of a solution procedure to address the computation challenges presented by the MSSP. The solution procedure uses a branch and bound approach to gradually solve the MSSP formulation. The first step in the development of this procedure was to develop a way to quick generate a feasible solution. To do this I developed two heuristic approaches. The first heuristic approach decomposed the original problem into a series of two-stage stochastic problems (Christian & Cremaschi, 2015).The benefit of this approach is that the number of constraints in each of the problems solved was reduced, however the number of scenarios in the problem caused the approach to quickly become computationally intractable. The second approach decomposed the problem into a series of knapsack problems (Christian & Cremaschi, 2015). Unlike the two-stage decomposition the knapsack did not need the full set of scenarios and was able to generate solutions for very large MSSPs. To complement the feasible solution it was important to develop an approach for solving a relaxed version of the problem. Currently my research focuses on the development of a progressive hedging based approach to solve a relaxed version of the MSSP. The benefit of using progressive hedging is that approach is highly parallelizable.

 Continued growth in the computational abilities of computers has opened the door for the use of large datasets in the development of chemical engineering models and optimization. Going forward, an increased understanding of how datasets can be incorporated into existing optimization frameworks will become increasingly important. In my future work I plan to be use my knowledge of statistics, programming, optimization, and graph theory to facilitate the advancement and development of new approaches to incorporating large data sets into chemical engineering applications.

Christian, B., & Cremaschi, S. (2015). Heuristic solution approaches to the pharmaceutical R&D pipeline management problem. Computers and Chemical Engineering, 74, 34â??47.

Colvin, M., & Maravelias, C. T. (2008). A stochastic programming approach for clinical trial planning in new drug development. Computers & Chemical Engineering, 32, 2626â??2642. http://doi.org/10.1016/j.compchemeng.2007.11.010

Goel, V., & Grossmann, I. E. (2006). A Class of Stochastic Programs with Decision Dependent Uncertainty. Mathematical Programming, 108(2), 355â??394.

Gupta, V., & Grossmann, I. E. (2011). Solution strategies for multistage stochastic programming with endogenous uncertainties. Computers and Chemical Engineering, 35(11), 2235â??2247. http://doi.org/10.1016/j.compchemeng.2010.11.013

Teaching Interests:

During my graduate studies I have had the opportunity to be a teaching assistant. As a teaching assisant I worked under a faculty advisor to develop assignments and lesson plans to engage students. My goal as a teacher will be to develop a program that promotes curiousity and a desire for life long learning. To do this I plan on incorporating real life examples and hands on learning to develop student passion for chemical engineering.