# (682e) A Graph Theory Approach to Non-Anticipativity Constraint Generation in Multistage Stochastic Programs with Incomplete Scenario Sets

#### AIChE Annual Meeting

#### 2016

#### 2016 AIChE Annual Meeting

#### Computing and Systems Technology Division

#### Design and Operations Under Uncertainty II

#### Thursday, November 17, 2016 - 1:46pm to 2:05pm

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

References

Colvin, M., & Maravelias, C. T. (2008). A

stochastic programming approach for clinical trial planning in new drug

development. *Computers & Chemical Engineering*, *32*, 2626–2642.

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.

Apap, R. M. & Grossmann, I. E. (2015). Models and computational

strategies for multistage stochastic programming under endogenous and exogenous

uncertainties. Manuscript in preparation.