Optimization Online


A Benders squared (B2) framework for infinite-horizon stochastic linear programs

Giacomo Nannicini (nannicini***at***us.ibm.com)
Emiliano Traversi (traversi***at***lipn.fr)
Roberto Wolfler Calvo (wolfler***at***lipn.fr)

Abstract: We propose a nested decomposition scheme for infinite-horizon stochastic linear programs. Our approach can be seen as a provably convergent extension of stochastic dual dynamic programming to the infinite-horizon setting: we explore a sequence of finite-horizon problems of increasing length until we can prove convergence with a given confidence level. The methodology alternates between a forward pass to explore sample paths and determine trial solutions, and a backward to generate a polyhedral approximation of the optimal value function by computing subgradients from the dual of the scenario subproblems. A computational study on a large set of randomly generated instances for two classes of problems shows that the proposed algorithm is able to effectively solve instances of moderate size to high precision, provided that the instance structure allows the construction of stationary policies with satisfactory objective function value.

Keywords: Benders Decomposition Stochastic Programming Cutting Planes

Category 1: Stochastic Programming

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 06/26/2017
Entry Accepted: 06/26/2017
Entry Last Modified: 04/18/2019

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