An Efficient Branch-and-Bound Strategy for Multistage Stochastic Programs with Endogenous and Exogenous Uncertainties

An efficient branch-and-bound strategy for multistage stochastic programs with endogenous and exogenous uncertainties

Robert M. Apap & Ignacio E. Grossmann

Multistage stochastic programming with both endogenous and exogenous uncertain parameters presents many unique challenges in terms of the development of efficient models and solution methods. Apap and Grossmann (2015) recently addressed some of these challenges; specifically, by developing theoretical reduction properties that can eliminate all redundant non-anticipativity constraints (NACs), and by proposing a sequential scenario decomposition heuristic that can quickly determine high-quality feasible solutions. Efficient decomposition methods such as this heuristic are essential for problems with endogenous and exogenous uncertainties, as the corresponding models are often extremely large, even after redundant NACs have been removed.

Although the sequential scenario decomposition heuristic is capable of providing both upper and lower bounds, it is not an exact solution method that can be used in an iterative procedure to converge to the optimal solution. One rigorous decomposition method that satisfies such criteria, and has also been applied successfully to this class of problems (Apap and Grossmann (2015)), is Lagrangean decomposition. In general, however, there will be a duality gap between the best Lagrangean bound and the best feasible solution that may be very difficult (or impossible) to sufficiently close with standard techniques. This is not uncommon in large stochastic programs where optimal, or near-optimal, solutions are required. To close the duality gap, one can employ a branch-and-bound strategy that uses Lagrangean-relaxation bounds rather than LP bounds (Guignard, 2003). A well-known example of this in stochastic programming is Carøe and Schultz (1999). Goel and Grossmann (2006) and Goel et al. (2006) later proposed a similar Lagrangean-duality-based branch-and-bound algorithm that can also handle endogenous uncertainties.

In this work, we update the algorithm of Goel and Grossmann (2006) and Goel et al. (2006) to take advantage of recent advances in the modeling of endogenous and exogenous uncertainties. Two of these advances include the scenario grouping approach of Gupta and Grossmann (2014) to strengthen the Lagrangean-dual bound, and the heuristic of Apap and Grossmann (2015) to provide a warm-start for the branch and bound. As an illustrative example, we apply this procedure to a large instance of an oilfield development planning problem.

References:

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

Carøe, C. C. & Schultz, R. (1999). Dual decomposition in stochastic integer programming. Operations Research Letters, 24, 37-45.

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

Goel, V., Grossmann, I. E., El-Bakry, A. S., & Mulkay, E. L. (2006). A novel branch and bound algorithm for optimal development of gas fields under uncertainty in reserves. Computers and Chemical Engineering, 30, 1076-1092.

Guignard, M. (2003). Lagrangean Relaxation. TOP, 11 (2), 151-228.

Gupta, V. & Grossmann, I. E. (2014). A new decomposition algorithm for multistage stochastic programs with endogenous uncertainties. Computers and Chemical Engineering, 62, 62-79.