We describe a generalization of Benders' method for solving two-stage stochastic linear optimization problems in which there are both continuous and integer variables in the first and second stages. Benders' method relies on finding effective lower approximations for the value function of the second-stage problem. In this setting, the value function is a discontinuous, non-convex, piecewise polyhedral function in general. To obtain a convergent algorithm, we employ the strong dual functions encoded in the branch-and-bound trees resulting from solution of the second-stage problem. We show that these can be used effectively within Benders' framework and describe a method for obtaining all required dual functions from a single, continuously refined branch-and-bound tree that is used to warm start the solution procedure for each subproblem. Finally, we show that this procedure allows us to conclude there exists a single branch-and-bound tree that encodes the full value function.
Citation
Laboratory for Computation Optimization at Lehigh (COR@L), Department of Industrial and Systems Engineering, Lehigh University, Technical Report 14T-005