State partitioning based linear program for stochastic dynamic programs: An invariance property Academic Article uri icon


  • A common approximate dynamic programming method entails state partitioning and the use of linear programming, i.e., the state-space is partitioned and the optimal value function is approximated by a constant over each partition. By minimizing a positive cost function defined on the partitions, one can construct an upper bound for the optimal value function. We show that this approximate value function is independent of the positive cost function and that it is the least upper bound, given the partitions. 2012 Elsevier B.V. All rights reserved.

published proceedings

  • Operations Research Letters

author list (cited authors)

  • Park, M., Krishnamoorthy, K., Darbha, S., Chandler, P., & Pachter, M.

citation count

  • 3

complete list of authors

  • Park, M||Krishnamoorthy, K||Darbha, S||Chandler, P||Pachter, M

publication date

  • November 2012