Relaxations of Weakly Coupled Stochastic Dynamic Programs

Daniel Adelman () and Adam J. Mersereau ()
Additional contact information
Daniel Adelman: Graduate School of Business, University of Chicago, Chicago, Illinois 60637
Adam J. Mersereau: Kenan-Flagler Business School, University of North Carolina, Chapel Hill, North Carolina 27599

Operations Research, 2008, vol. 56, issue 3, 712-727

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

Keywords: dynamic programming/optimal control; approximate dynamic programming; Lagrangian optimization; discounted infinite horizon; linear programming; column generation (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (44)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0445 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:56:y:2008:i:3:p:712-727

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().