*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
We consider a class of stochastic dynamic programming problems that are amenable to relaxation via decomposition. We compare two techniques under an additively separable value function approximation, namely Lagrangian relaxation and the linear programming (LP) approach to approximate dynamic programming. We prove that the linear programming-based approximate dynamic programming method achieves tighter bounds than the Lagrangian relaxation. We also investigate the gap between the two bounds, proving conditions under which both are tight, and providing an example in which the gap may be arbitrarily large. Algorithmically, we show how the computationally more complex LP can be solved using column generation. Computational results on several sets of problem instances show that the LP-based method results in better policies, and that the differences in the bounds depend on the nature of the underlying constraints being relaxed. We consider a class of stochastic dynamic programming problems that are amenable to relaxation via decomposition. We compare two techniques under an additively separable value function approximation, namely Lagrangian relaxation and the linear programming (LP) approach to approximate dynamic programming. We prove that the linear programming-based approximate dynamic programming method achieves tighter bounds than the Lagrangian relaxation. We also investigate the gap between the two bounds, proving conditions under which both are tight, and providing an example in which the gap may be arbitrarily large. Algorithmically, we show how the computationally more complex LP can be solved using column generation. Computational results on several sets of problem instances show that the LP-based method results in better policies, and that the differences in the bounds depend on the nature of the underlying constraints being relaxed.
