A finite $$\epsilon $$ϵ-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables

Can Li and Ignacio E. Grossmann ()
Additional contact information
Can Li: Carnegie Mellon University
Ignacio E. Grossmann: Carnegie Mellon University

Journal of Global Optimization, 2019, vol. 75, issue 4, No 2, 947 pages

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

Keywords: Stochastic programming; Integer recourse; Generalized Benders decomposition; Branch and bound (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-019-00820-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:75:y:2019:i:4:d:10.1007_s10898-019-00820-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-019-00820-y

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().