-

 

 

 




Optimization Online





 

Stochastic Dual Dynamic Integer Programming

Jikai Zou (jikai.zou***at***gatech.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
Xu Andy Sun (andy.sun***at***isye.gatech.edu)

Abstract: Multistage stochastic integer programming (MSIP) combines the difficulty of uncertainty, dynamics, and non-convexity, and constitutes a class of extremely challenging problems. A common formulation for these problems is a dynamic programming formulation involving nested cost-to-go functions. In the linear setting, the cost-to-go functions are convex polyhedral, and decomposition algorithms, such as nested Benders’ decomposition and its stochastic variant - Stochastic Dual Dynamic Programming (SDDP) - that proceed by iteratively approximating these functions by cuts or linear inequalities, have been established as effective approaches. It is difficult to directly adapt these algorithms to MSIP due to the nonconvexity of integer programming value functions. In this paper we propose an extension to SDDP – called stochastic dual dynamic integer programming (SDDiP) – for solving MSIP problems with binary state variables. The crucial component of the algorithm is a new class of cuts, termed Lagrangian cuts, derived from a Lagrangian relaxation of a specific reformulation of the subproblems in each stage, where local copies of state variables are introduced. We show that the Lagrangian cuts satisfy a tightness condition and provide a rigorous proof of the finite convergence of SDDiP with probability one. We show that, under fairly reasonable assumptions, a MSIP problem with general state variables can be approximated by one with binary state variables to desired precision with only a modest increase in problem size. Thus our proposed SDDiP approach is applicable to very general classes of MSIP problems. Extensive computational experiments on three classes of real-world problems, namely electric generation expansion, financial portfolio management, and network revenue management, show that the proposed methodology is very effective in solving large-scale, multistage stochastic integer optimization problems.

Keywords: multistage stochastic integer programming, binary state variables, nested decomposition, stochas- tic dual dynamic programming

Category 1: Stochastic Programming

Category 2: Integer Programming

Category 3: Other Topics (Dynamic Programming )

Citation: Submitted for publication, 2016.

Download: [PDF]

Entry Submitted: 05/11/2016
Entry Accepted: 05/11/2016
Entry Last Modified: 03/28/2017

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
Mathematical Optimization Society