A finite ∈-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary 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 mixed-binary nonlinear stochastic programs with mixed-binary 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 in conjunctive normal form (CNF). Second, we apply basic steps to convert the CNF of the MINLP subproblem into disjunctive normal form 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-binary 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 an optimal solution. We prove that the algorithm GBDBAB can converge to epsilon-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 on a problem with quadratic constraints, a constrained layout problem, and a planning problem, demonstrate the effectiveness of the algorithm.