Optimization Online


Stochastic Lipschitz Dynamic Programming

Shabbir Ahmed (shabbir.ahmed***at***isye.gatech.edu)
Filipe G. Cabral (filipegoulartcabral***at***poli.ufrj.br)
Bernardo Freitas Paulo da Costa (bernardofpc***at***im.ufrj.br)

Abstract: We propose a new algorithm for solving multistage stochastic mixed integer linear programming (MILP) problems with complete continuous recourse. In a similar way to cutting plane methods, we construct nonlinear Lipschitz cuts to build lower approximations for the non-convex cost to go functions. An example of such a class of cuts are those derived using Augmented Lagrangian Duality for MILPs. The family of Lipschitz cuts we use is MILP representable, so that the introduction of these cuts does not change the class of the original stochastic optimization problem. We illustrate the application of this algorithm on two simple case studies, comparing our approach with the convex relaxation of the problems, for which we can apply SDDP, and for a discretized approximation, applying SDDiP.

Keywords: Stochastic Programming, Mixed-Integer optimization, augmented duality, dynamic programming

Category 1: Stochastic Programming

Category 2: Integer Programming

Category 3: Other Topics (Dynamic Programming )

Citation: Submitted for publication, 2019

Download: [PDF]

Entry Submitted: 05/06/2019
Entry Accepted: 05/06/2019
Entry Last Modified: 05/22/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