(669a) Multi-Stage Scenario Tree Generation for Reliable Production Planning of Integrated Sites Under Uncertainty

Calfa, B. A., University of Wisconsin at Madison
Agarwal, A., Carnegie Mellon University
Grossmann, I. E., Carnegie Mellon University
Wassick, J. M., The Dow Chemical Company
Bury, S. J., Dow Inc.
Czyzyk, J. J., The Dow Chemical Company

Production planning decisions usually span multiple time periods and generally involve, but are not limited to, determining the amount of raw materials to be purchased by each plant, the production and inventory levels at each plant, the transportation of intermediate and finished products between different locations, and meeting the forecast demand. It is clear that all of those decisions may be subject to some kind of uncertainty. For instance, the availability of a key raw material may be uncertain, i.e. there may be shortage for certain months in a year. Another example is the possibility of mechanical failure of pieces of equipment in a plant or its complete unplanned shutdown, which affects the entire network. Two types of uncertainties are reported in the literature (Goel & Grossmann, 2006): exogenous (e.g., market) and endogenous (e.g., decision-dependent). A review on optimization methods with exogenous uncertainties can be found in Sahinidis (2004).

The system under consideration is a network of chemical plants in geographically distributed sites that are supplemented by material imported from either external suppliers or other integrated sites. The chemical plants in each site are highly integrated. The objective in this project is to develop optimization methods that predict production planning, allocation, and sourcing decisions for the complex integrated multi-site product envelopes, and also effectively manage multiple sources of uncertainty in the data. A Multi-Stage Stochastic Programming (MSSP) model (Birge & Louveaux, 1997) was developed.

A major focus of this work is to devise methods to quantify the uncertainty in the data so that it can be properly integrated in the stochastic programming model. This amounts to generating scenario trees that best represent the variability in the historical data. It is important to recall the purpose of using scenario trees in Stochastic Programming (SP) (Kaut, 2003). Scenario trees are an approximate discretized representation of the uncertainty in the data. They are based on discretized probability distributions to model the stochastic processes. The scenario trees are approximate because they contain a restricted number of outcomes in order to yield tractable SP models. The complexity of the scenario trees directly impacts the computational complexity of SP models.

The moment matching method, originally proposed by Høyland & Wallace (2001), can be used to generate scenario trees. Given an initial structure of the tree, i.e. number of nodes per stage, it attempts to assign the values for the random variables in each node and the probabilities of each outcome by solving a nonlinear optimization (NLP) problem. The NLP problem minimizes the squared error between some statistical properties calculated from the scenario tree and the same properties calculated directly from the data. Examples of statistical properties are the first four moments (expected value, variance, skewness, and kurtosis), covariance or correlation matrix, percentiles, etc.

The complexity of generating satisfactory scenario trees for MSSPs lies in the multi-stage aspect of the problem. For instance, the outcomes at the third stage are conditional on the outcomes at the second stage and so forth. Therefore, the correlations between consecutive stages should be considered in order to generate a more accurate scenario tree. In this work, we extend the moment matching method to include the dependency across stages through autocorrelations between the random variables that can be obtained after fitting a time-series model to the historical data. It is shown that the model can still be formulated as an NLP problem. We present several results of process network problems that show that by updating probabilities using Bayesian analysis, while generating the scenario tree, yields higher expected profit than if no information is updated through time. The significance of this work is that it addresses the important issue of deciding the correct structure and probabilities associated with the scenario tree, which in most cases is simply assumed to be given.


Birge, J. R., and Louveaux, F. 1997. Introduction to Stochastic Programming. Springer-Verlag New York, Inc.

Goel, V., and Grossmann, I. E. 2006. A Class of Stochastic Programs with Decision Dependent. Mathematical Programming. 108(2-3):355–394.

Høyland, K., and Wallace, S. W. 2001. Generating Scenario Trees for Multistage Decision Problems. Management Science. 46(2):295–307.

Kaut, M. (2003). Scenario tree generation for stochastic programming: Cases from finance. Ph.D. Thesis. Norwegian University of Science and Technology.

Sahinidis, N. V. 2004. Optimization Under Uncertainty: State-of-the-Art and Opportunities. Computers & Chemical Engineering. 28(6-7):971–983.