61647
event
1286537869
1475891559
<![CDATA[ISyE Seminar Series :: Relaxations of Weakly Coupled Stochastic Dynamic Programs (work with Dan Adelman)]]>
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 programmingbased 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 LPbased 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 programmingbased 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 LPbased method results in better policies, and that the differences in the bounds depend on the nature of the underlying constraints being relaxed. ]]>





Barbara Christopher
Industrial and Systems Engineering
Contact Barbara Christopher
404.385.3102]]>




<![CDATA[]]>


 1242

1795