What is the importance of dynamic programming in OR?

And is it different from time series analysis and planning ?

To me the word "dynamic" makes no sense about what exactly this programming means.

I request all the members to kindly clarify my confusion.

thank you so much in advance

asked 08 Jan '12, 10:49

Ram's gravatar image

Ram
51941029
accept rate: 0%

edited 08 Jan '12, 12:49

fbahr's gravatar image

fbahr ♦
4.6k716


Dynamic programming refers to optimization over multiple stages. You can read about the choice of the name http://www.wu.ac.at/usr/h99c/h9951826/bellman_dynprog.pdf It has little to do with time series analysis.

link

answered 08 Jan '12, 11:16

Michael%20Trick's gravatar image

Michael Trick ♦♦
4.1k41533
accept rate: 20%

  1. [Importance?] The same as divide-and-conquer, backtracking, greedy, and such. DP is an algorithm design paradigm, i.e., a "template" that has to "instantiated" with some purpose-specific "concepts" (like objective function, decision stages, stage-wise alternatives, etc.) to become useful. Some examples of DP-based algorithms are listed here and here.

  2. [Different from time-series analysis and...?] Yes. (See above.)

  3. [Meaning of "dynamic"?] Also taken from the Wikipedia article on DP: "The term dynamic programming was originally used in the 1940s by Richard Bellman to describe the process of solving problems where one needs to find the best decisions one after another. By 1953, he refined this to the modern meaning, referring specifically to nesting smaller decision problems inside larger decisions. [...] The word dynamic was chosen by Bellman to capture the time-varying aspect of the problems, and also because it sounded impressive. [The word programming referred to the use of the method to find an optimal program, in the sense of a military schedule for training or logistics. This usage is the same as that in the phrases linear programming and mathematical programming, a synonym for mathematical optimization.]" (see also: DP as introduced in CLRS).

link

answered 08 Jan '12, 11:23

fbahr's gravatar image

fbahr ♦
4.6k716
accept rate: 13%

edited 08 Jan '12, 11:33

Ram, you are in good company. Recently, the mathematical programming society changed its name into mathematical optimization society (MOS, http://www.mathopt.org/) for a similar reason: people are confused (at best) about the name "programming".

link

answered 08 Jan '12, 11:24

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×127
×53
×9

Asked: 08 Jan '12, 10:49

Seen: 1,816 times

Last updated: 08 Jan '12, 12:49

OR-Exchange! Your site for questions, answers, and announcements about operations research.