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.