(441c) On Solving Nonconvex Two-Stage Stochastic Programs with Generalized Benders Decomposition

Stochastic programming is one of the major mathematical frameworks in the area of decision-making under uncertainty. A special case is two-stage stochastic programming in which stage-one decisions correspond to “here and-now” decisions that must be taken before the uncertainties are revealed; stage-two decisions correspond to “wait and see” decisions or recourse decisions that can be adjusted in the face of the realization of the uncertainties.. Solving the deterministic equivalent of the two-stage stochastic programs directly can be prohibitive when the number of scenarios is large because the computational time generally grows exponentially with the number of scenarios. Generalized Benders decomposition ^[1] can be applied to problems with continuous variables and convex constraints in the second stage. However, it cannot be applied directly to the problems with nonconvex second stage constraints.

In the area of nonconvex nonlinear stochastic programming, Li et al ^[2] has proposed a NGBD algorithm for problems with pure binary first stage variables. Cao and Zavala ^[3] propose a scalable algorithm that can globally optimize nonconvex two-stage stochastic programs. Ogbe and Li ^[4] propose a joint decomposition algorithm for general mixed-integer nonlinear nonconvex stochastic programs.

In this work, we further explore algorithms based on generalized Benders decomposition for solving two-stage stochastic programs with nonconvex constraints and mixed-integer variables in both first and second stage decisions. The validity and tightness of different types of cuts including Benders cuts, strengthened Benders cuts, and Lagrangean cuts are studied. Moreover, different convexification schemes for nonconvex problems are tested under this framework. In order for the algorithm to have finite convergence, a spatial branch and bound search is performed on the first stage decisions.

The algorithm is tested with several applications in process systems engineering, that includes the generalized pooling problem under uncertainty. The decomposition algorithm is benchmarked against the full-space solution with state-of-art global solvers, such as BARON, ANTIGONE.

[1] Arthur M. Geoffrion "Generalized benders decomposition. Journal of Optimization Theory and Applications 237-260, 1972.

[2] Xiang Li, Asgeir Tomasgard, and Paul I Barton. Nonconvex generalized benders decompo-sition for stochastic separable mixed-integer nonlinear programs. Journal of Optimization Theory and Applications, 151(3):425, 2011.

[3] Yankai Cao and Victor M Zavala. A scalable global optimization algorithm for stochastic nonlinear programs. Under Review, 2017.

[4] Emmanuel Ogbe and Xiang Li. A joint decomposition method for global optimization of multiscenario nonconvex mixed-integer nonlinear programs. arXiv preprint arXiv:1802.07342, 2018.