470526 A Graph Theory Approach to Non-Anticipativity Constraint Generation in Multistage Stochastic Programs with Incomplete Scenario Sets
Multistage stochastic programs (MSSPs) with endogenous uncertainty arise from problem where the revelation of uncertainty is decision-dependent, such as 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). The MSSPs grow exponentially with the number of uncertain parameters and the number of realizations for each uncertain parameter. More specifically, the number of uncertain parameters and the number of realizations increase the number of scenarios in the model. The scenarios for the full-space model are generated using the Cartesian product of the realizations of the uncertain parameters. The size of the decision variables and the number of non-anticipativity constraints (NACs) increase with the increasing in the number of scenarios. 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 address the complexity is to solve them using sample average approximation approaches where a subsets of scenarios generated from the full scenario set is considered. The solutions can be used to generate bounds for the full space problem, or can be implemented as heuristics. The challenge with this approach is that the traditional NAC reduction procedures are not applicable when only subsets of scenarios are used (Apap and Grossmann, 2015).
In this talk, we present a graph theory based algorithm, Sample Non-Anticipativity Constraint algorithm (SNAC), to determine the minimum number of NACs for the scenario subsets, and to efficiently generate at least one of the corresponding feasible NAC sets. The SNAC assumes that the scenarios are a subset of the full space scenario set, and that that the full space scenario set can be projected onto n-dimensional integer lattice, where n represents the number of uncertain parameters. This projection simply requires that the realizations of each uncertain parameter can be mapped to an integer range with a length equal to the number of realizations. The mapping allows the generation of an n-tuple representing the position of a scenario on the integer lattice.
The first step of the SNAC algorithm is to map the subset of scenarios to the full space integer lattice. The algorithm then adds edges to the lattice until the lattice forms a minimum spanning tree (MST) for the subset. The weight of each edge is set to its Euclidian distance for generating the MST. Using a MST connection, the procedure prioritizes connections of adjacent nodes and eliminates the need for redundant connections. The edges added in the generation of the MST represent the NACs needed to relate the selected scenarios. If the problem has only one stage of realizations (i.e., the problem is a two-stage stochastic problem), the added constraints also represent all the full set of NACs needed for the problem.
In MSSPs, when a realization occurs the scenario set is divided to form subsets. In order to achieve a feasible solution, all scenarios in each subset must be connected with proper NACs. The SNAC algorithm uses the MST generation procedure to generate the connections for each subset. To ensure that connections exist for any possible subset, the SNAC algorithm iterates over the possible subsets. To facilitate the enumeration of the subsets, the algorithm exploits the integer lattice mapping, which ensures that the division of the scenarios into subsets always occurs perpendicular to the plane of the realized uncertain parameter. For each subset, the algorithm reduces the number of NACs by using connections that were generated in previous subsets.
Figure 1 shows the results of applying the algorithm four times. In each application, samples of four scenarios selected from an MSSP with two uncertain parameters, and , and three realizations each. In Figure 1, the shaded dots represent the sampled scenarios. The row and column in which each scenario appears corresponds to the realized values of the uncertain parameters. The lines connecting scenarios represent the NACs generated by the algorithm. In each of the cases the algorithm prioritizes connecting selected scenarios that are adjacent. In Figure 1(A), the initial MST connects scenarios in the first row because they are adjacent. The algorithm then connects the scenarios in the third column. When the algorithm generates all the possible subsets of scenarios, no additional NACs are needed. Similarly, in Figure 1(B), the SNAC algorithm yields NACs corresponding to connections of all adjacent scenarios. Then, a diagonal connection ensures non-anticipativity between the scenarios in the third column and the second column. Again, when subsets are generated no new NAC are needed. Figure 1(C) represents a subset where all scenarios are adjacent. The algorithm is able to generate all the NACs simply by connecting all adjacent scenarios. Figure 1(D) in contrast has only one pair of adjacent scenarios. The other two scenarios are connected to the adjacent pair with a horizontal line and a diagonal line to form the initial MST. When the algorithm iterates over the subsets, the two non-adjacent scenarios must be connected.
The talk will introduce the algorithm in detail, and demonstrate its application using the general two uncertain parameter problem, and, three uncertain parameter problem. We will present the generalization of the algorithm to an n uncertain parameter case, and compare the number of NACs generated using SNAC to the standard approaches. A preliminary analysis of the algorithm shows that the generation of the NACs occurs in polynomial time. In future, we plan to implement the SNAC algorithm for developing a sample average approximation approach to solve MSSPs.
Figure 1 Non-anticipativity constraints generated using the SNAC algorithm
Colvin, M., & Maravelias, C. T. (2008). A stochastic programming approach for clinical trial planning in new drug development. Computers & Chemical Engineering, 32, 26262642.
Goel, V., & Grossmann, I. E. (2006). A Class of Stochastic Programs with Decision Dependent Uncertainty. Mathematical Programming, 108(2), 355394.
Gupta, V., & Grossmann, I. E. (2011). Solution strategies for multistage stochastic programming with endogenous uncertainties. Computers and Chemical Engineering, 35(11), 22352247.
Apap, R. M. & Grossmann, I. E. (2015). Models and computational strategies for multistage stochastic programming under endogenous and exogenous uncertainties. Manuscript in preparation.