(635g) 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.