A finite ε-convergence algorithm for two-stage convex 0-1 mixed-integer nonlinear stochastic programs with mixed-integer first and second stage variables

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.

Article

Download

View PDF