ISyE Seminar Series :: Relaxations of Weakly Coupled Stochastic Dynamic Programs (work with Dan Adelman)

Event Details
  • Date/Time:
    • Thursday January 19, 2006 - Wednesday January 18, 2006
      10:00 am - 11:00 pm
  • Location: Executive Classroom (Room 228 Main Building)
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
Barbara Christopher
Industrial and Systems Engineering
Contact Barbara Christopher
404.385.3102
Summaries

Summary Sentence: ISyE Seminar Series :: Relaxations of Weakly Coupled Stochastic Dynamic Programs (work with Dan Adelman)

Full Summary: 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 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.

Additional Information

In Campus Calendar
No
Groups

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Barbara Christopher
  • Workflow Status: Published
  • Created On: Oct 8, 2010 - 7:37am
  • Last Updated: Oct 7, 2016 - 9:52pm