  


A finite εconvergence algorithm for twostage convex 01 mixedinteger nonlinear stochastic programs with mixedinteger first and second stage variables
Can Li(canl1andrew.cmu.edu) Abstract: In this paper, we propose a generalized Benders decompositionbased branch and bound algorithm, GBDBAB, to solve twostage convex 01 mixedinteger nonlinear stochastic programs with mixedinteger variables in both first and second stage decisions. In order to construct the convex hull of the MINLP subproblem for each scenario in closedform, 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 closedform. However, for problems with mixedinteger 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 Citation: Download: [PDF] Entry Submitted: 03/07/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  