Solution strategies for multistage stochastic programming with endogenous uncertainties

In this paper, we present a generic mixed-integer linear multistage stochastic programming (MSSP) model considering endogenous uncertainty in some of the parameters. To address the issue that the number of non-anticipativity (NA) constraints increases exponentially with the number of uncertain parameters and/or its realizations, we present a new theoretical property that significantly reduces the problem size and complements two previous properties. Since one might generate reduced models that are still too large to be solved directly, we also propose three solution strategies: a k-stage constraint strategy where we only include the NA constraints up to a specified number of stages, an iterative NAC relaxation strategy, and a Lagrangean decomposition algorithm that decomposes the problem into scenarios. Numerical results for two process network examples are presented to illustrate that the proposed solution strategies yield significant computational savings.

Research highlights▶ Multistage programming model where structure of scenario tree depends on timing of decisions. ▶ New theoretical property reduces potentially large number of non-anticipativity constraints. ▶ New algorithms allow efficient solution of multistage stochastic programs. ▶ Theory and algorithms applied to multiperiod planning of process networks with uncertain yields.