(269c) Solution Strategies for Multistage Stochastic Programming in the Planning of Process Networks Under Endogenous Uncertainties

Synthesis of process networks and capacity planning under uncertainty has been a very active area of research in the last few decades. Modeling and solution of this class of problems by stochastic programming, which directly takes uncertainty into account in terms of probability distribution functions (Birge & Louveaux, 1997), is receiving increasing attention given the limitations of the deterministic models. Jonsbraten (1998) classified uncertainty in Stochastic Programming problems into two broad categories: exogenous uncertainty (e.g. demands) where stochastic processes are independent of decisions that are taken, and endogenous uncertainty (e.g. yields) where stochastic processes are affected by these decisions. In this paper, we focus on problems with endogenous uncertainty for which there is very limited literature available.

Recently, few practical applications that involve multistage stochastic programming with endogenous uncertainty have been addressed. Goel & Grossmann (2004) dealt with the gas field development problem under uncertainty in size and quality of reserves where decisions on the timing of field drilling yield an immediate resolution of the uncertainty. These authors developed two theoretical properties and a Lagrangean decomposition based branch and bound solution method. Tarhan & Grossmann (2008) applied endogenous uncertainty in the synthesis of process networks problem with uncertain yield and used gradual uncertainty resolution in the model. Boland et al. (2008) addressed open pit mine production scheduling problem considering endogenous uncertainty in the total amount of rock and metal contained in it, where the excavation decisions resolve this uncertainty. Colvin & Maravelias (2010) presented several theoretical properties, specifically to the problem of scheduling of clinical trials having uncertain outcomes in the pharmaceutical R&D pipeline and developed a branch and cut framework to solve these MSSP problems with endogenous uncertainty.

In this paper, we present a Multistage Stochastic Programming (MSSP) model based on Goel and Grossmann (2006) and solution strategies for the long-term planning (i.e. investment, operation decisions) of process networks considering endogenous uncertainty in the process yields. The key issue with this model is that the number of constraints, especially non-anticipativity (NA) constraints that are essential in the model to ensure that current decisions do not anticipate future outcomes, increases exponentially with the number of uncertain parameters and/or its realizations. Therefore, the problem can become intractable to solve directly using commercial solvers. To address this issue, we present a new theoretical property that significantly reduces the problem size and complements two previous properties presented by Goel and Grossmann (2006). The reduced model obtained by using these properties can be solved in reasonable time compared to the original model.

However, even with the proposed reduction scheme one might generate problems that prove to be too large to be solved directly. Therefore, we also propose solution strategies to solve large-scale problems in this class. The first strategy, that is based on the idea that most of the investment decisions occurs in the early stages of the planning horizon, is the k-stage constraint strategy where we only include the NA constraints up to a specified number of stages in the reduced model instead of the all stages. The resulting k-stage constraint model provides a strong lower bound to the original problem and its solution is also the optimum solution to the original problem in special cases. The motivation for the second proposed solution strategy, NAC relaxation strategy, comes from the fact that very few inequality NA constraints remain active in the optimal solution of the problem. In this strategy, initially all inequality NA constraints are removed from the model and LP relaxation of the resulting model is solved and violated NA constraints are added iteratively until there is no violation of these constraints in the LP relaxation. Then, the resulting model with the added cuts is solved as an MILP problem to obtain the lower bound and generate feasible solution. It has been observed that very few inequality NA constraints (~6-7%) are added as cuts in this procedure. Finally, a Lagrangean decomposition algorithm is also presented that decomposes the problem into scenarios yielding a lower bound on the objective function, while the upper bound is generated by using a heuristic based on the solution of the relaxed problem. The gap between the upper and lower bounds at the root node is rather small in most of the cases. Numerical results for two process network examples are presented to illustrate the proposed solution strategies and results show that significant computational savings can be achieved. Moreover, the proposed solution strategies are also applicable to a wide range of other problems that require decision-making in the presence of uncertainty.

References:

1) Birge, J. R., Louveaux, F., 1997. Introduction to stochastic programming. New York, NY: Springer.

2) Boland, N., Dumitrescu, I., Froyland, G., 2008. A multistage stochastic programming approach to open pit mine production scheduling with uncertain geology. http://www.optimizationonline.org/DBHTML/2008/10/2123.html.

3) Colvin, M., Maravelias, C. T., 2010. Modeling methods and a branch and cut algorithm for Pharmaceutical Clinical Trial Planning using Stochastic Programming, European Journal of Operational Research, 203 (2010) 205?215.

4) Goel, V., Grossmann, I. E., 2004. A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Computers and Chemical Engineering 28 (8), 1409?1429.

5) Goel, V., Grossmann, I. E., 2006. A class of stochastic programs with decision dependent uncertainty. Mathematical Programming 108 (2-3, Ser. B), 355-394.

6) Jonsbraten, T.W., Wets, R.J. B., Woodruff, D.L., 1998. A class of stochastic programs with decision dependent random elements. Annals of Operations Research 82, 83-106.

7) 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. Computers and Chemical Engineering 32, 766-788.