Optimization Online


A Generalization of Benders' Algorithm for Two-Stage Stochastic Optimization Problems With Mixed Integer Recourse

Anahita Hassanzadeh(anahita.hassanzadeh***at***gmail.com)
Ted Ralphs(ted***at***lehigh.edu)

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

Keywords: Stochastic Integer Programming, Benders Decomposition

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Laboratory for Computation Optimization at Lehigh (COR@L), Department of Industrial and Systems Engineering, Lehigh University, Technical Report 14T-005

Download: [PDF]

Entry Submitted: 08/03/2014
Entry Accepted: 08/03/2014
Entry Last Modified: 08/03/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society