Optimization Online


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

Can Li (canl1***at***andrew.cmu.edu)
Ignacio Grossmann (grossmann***at***cmu.edu)

Abstract: 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.

Keywords: Stochastic programming  Nonconvex MINLP  Generalized Benders Decomposition  Cutting Planes

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 02/06/2019
Entry Accepted: 02/07/2019
Entry Last Modified: 02/07/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society