This Article Full Text (PDF) e-companion References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Adelman, D. Articles by Mersereau, A. J. Search for Related Content

Relaxations of Weakly Coupled Stochastic Dynamic Programs

Graduate School of Business, University of Chicago, Chicago, Illinois 60637
Kenan-Flagler Business School, University of North Carolina, Chapel Hill, North Carolina 27599
dan.adelman{at}chicagogsb.edu
ajm{at}unc.edu

We consider a broad class of stochastic dynamic programming problems that are amenable to relaxation via decomposition. These problems comprise multiple subproblems that are independent of each other except for a collection of coupling constraints on the action space. We fit an additively separable value function approximation using two techniques, namely, Lagrangian relaxation and the linear programming (LP) approach to approximate dynamic programming. We prove various results comparing the relaxations to each other and to the optimal problem value. We also provide a column generation algorithm for solving the LP-based relaxation to any desired optimality tolerance, and we report on numerical experiments on bandit-like problems. Our results provide insight into the complexity versus quality trade-off when choosing which of these relaxations to implement.

Subject classifications: dynamic programming/optimal control; approximate dynamic programming; Lagrangian optimization; discounted infinite horizon; linear programming; column generation.
History: Received June 2006; revision received October 2006; accepted January 2007.