Optimization Online


A finite ε-convergence algorithm for two-stage convex 0-1 mixed-integer nonlinear stochastic programs with mixed-integer first 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 bound algorithm, GBDBAB, to solve two-stage convex 0-1 mixed-integer nonlinear stochastic programs with mixed-integer variables in both first and second stage decisions. In order to construct the convex hull of the MINLP subproblem for each scenario in closed-form, we first represent each MINLP subproblem as a generalized disjunctive program (GDP) in conjunctive normal form (CNF). Second, we apply basic steps to convert the CNF of the MINLP subproblem into disjunctive normal form (DNF) to obtain the convex hull of the MINLP subproblem. We prove that GBD is able to converge for the problems with pure binary variables given that the convex hull of each subproblem is constructed in closed-form. However, for problems with mixed-integer first and second stage variables, we propose an algorithm, GBDBAB, where we may have to branch and bound on the continuous first stage variables to obtain the optimal solution. We prove that the algorithm GBDBAB can converge to ε-optimality in a finite number of steps. Since constructing the convex hull can be expensive, we propose a sequential convexification scheme that progressively applies basic steps to the CNF. Computational results demonstrate the effectiveness of the algorithm.

Keywords: Stochastic programming,  Integer recourse,  Generalized Benders decomposition,  Branch and bound

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 03/07/2018
Entry Accepted: 03/07/2018
Entry Last Modified: 03/07/2018

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