(682e) 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

 
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.