(282e) A Graph-Theory Approach for Efficient Non-Anticipativity-Constraint Reduction in Multistage Stochastic Programming Problems Involving Endogenous and Exogenous Uncertainties

A
graph-theory approach for efficient non-anticipativity-constraint reduction in
multistage stochastic programming problems involving endogenous and exogenous
uncertainties

Robert
M. Apap & Ignacio E. Grossmann

In
multistage stochastic programming problems, the number of non-anticipativity
constraints (NACs) grows rapidly as the number of time periods, uncertain
parameters, or realizations increases (Apap and Grossmann, 2015). It is
typically desirable to eliminate as many redundant NACs as possible. In the
case that the uncertainty is purely exogenous, this process is fairly
straightforward since the scenario tree is fixed. For the case of purely
endogenous uncertainty, however, the scenario tree is decision dependent; hence,
NAC elimination is considerably more involved. Previous works in the
literature, namely Goel and Grossmann (2006) and Gupta and Grossmann (2011), have
proposed effective theoretical reduction properties for this class of problems.
One primary assumption in these existing properties, though, is that the set of
scenarios corresponds to all possible combinations of realizations of the
uncertain parameters (i.e., a Cartesian product over all sets of realizations).
In large, real-world problems with many uncertain parameters, the
Cartesian-product approach can easily lead to instances with several thousands
of scenarios or more. These problems are generally intractable. Furthermore, if
some of the uncertain parameters are correlated, many of the scenarios in these
large problems may in fact refer to impossible outcomes.

In
this paper, we solve mixed-integer linear multistage stochastic programming
problems involving endogenous and exogenous uncertainties, where the scenario
sets are pre-specified and do not correspond to Cartesian products. These
arbitrary scenario sets can each be viewed as the result of sampling from a
joint probability distribution. Since the previous reduction properties in the
literature do not apply here, efficient generation of the non-anticipativity
constraints becomes a challenge. Khaligh and MirHassani (2015) recently addressed
this issue for multistage stochastic programming problems under endogenous
uncertainty and proposed a novel graph-theory approach for generating the
minimum number of NACs in polynomial time. In the current work, we extend their
approach to problems with both endogenous and exogenous uncertainties. We present
several illustrative examples related to process networks and oilfield
development planning in order to demonstrate the implementation of the proposed
reduction algorithm. These problems are then solved with a combination of a
fast heuristic and Lagrangean decomposition, as described in Apap and Grossmann
(2015).

References:

Apap,
R. M. & Grossmann, I. E. (2015). Models and computational strategies for
multistage stochastic programming under endogenous and exogenous uncertainties.
Manuscript in preparation.

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

Gupta,
V. & Grossmann, I. E. (2011). Solution strategies for multistage stochastic
programming with endogenous uncertainties. Computers and Chemical Engineering,
35, 2235-2247.

Khaligh,
F. H. & MirHassani, S. A. (2015). Efficient constraint reduction in
multistage stochastic programming problems with endogenous uncertainty. To
appear in Optimization Methods and Software.