Relaxations of weakly coupled stochastic dynamic programs

作     者：Adelman, Daniel Mersereau, Adam J. 

作者机构：Univ Chicago Grad Sch Business Chicago IL 60637 USA Univ N Carolina Kenan Flagler Business Sch Chapel Hill NC 27599 USA 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：2008年第56卷第3期

页      面：712-727页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：dynamic programming/optimal control: approximate dynamic programming Lagrangian optimization discounted infinite horizon linear programming: column generation 

摘      要：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.