(669g) A New Decomposition Algorithm for Multistage Stochastic Programs With Endogenous Uncertainties

Grossmann, I. E., Carnegie Mellon University
Gupta, V., Carnegie Mellon University

In this paper, we present a new decomposition algorithm for solving large-scale multistage stochastic programs (MSSP) with endogenous uncertainties. Instead of dualizing all the initial non-anticipativity constraints (NACs) and removing all the conditional non-anticipativity constraints to decompose the problem into scenario subproblems, the basic idea relies on keeping a subset of NACs as explicit constraints in the scenario group subproblems while dualizing or relaxing the rest of the NACs. It is proved that the algorithm provides a dual bound that is at least as tight as the standard approach. Numerical results for process network examples and oilfield development planning problem are presented to illustrate that the proposed decomposition approach yields significant improvement in the dual bound at the root node and reduction in the total computational expense for closing the gap.