A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary fi rst and second stage variables

In this paper, we propose a generalized Benders decomposition-based branch and cut algorithm for solving two stage stochastic mixed-integer nonlinear programs (SMINLPs) with mixed binary rst and second stage variables. At a high level, the proposed decomposition algorithm performs spatial branch and bound search on the rst stage variables. Each node in the branch and bound search is solved with a Benders-like decomposition algorithm where both Lagrangean cuts and Benders cuts are included in the Benders master problem. The Lagrangean cuts are derived from Lagrangean decomposition. The Benders cuts are derived from the Benders subproblems, which are convexifi ed by cutting planes, such as rank-one lift-and-project cuts. We prove that the proposed algorithm has convergence in the limit. We apply the proposed algorithm to a stochastic pooling problem, a crude selection problem, and a storage design problem. The performance of the proposed algorithm is compared with a Lagrangean decomposition-based branch and bound algorithm and solving the corresponding deterministic equivalent with the solvers including BARON, ANTIGONE, and SCIP.

Article

Download

View A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary fi rst and second stage variables