Relaxations of weakly coupled stochastic dynamic programs
成果类型：
Article
署名作者：
Adelman, Daniel; Mersereau, Adam J.
署名单位：
University of Chicago; University of North Carolina; University of North Carolina Chapel Hill
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1070.0445
发表日期：
2008
页码：
712-727
关键词：
摘要：
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.