3
$\begingroup$

Mostly when I search dynamic programming in google I get : dynamic programming (DP) in python, in C++, in java from web pages like geekforgeeks, litecode, codechef, and so on.

But in the operation research books (taha,lieberman) they use just analitical tools.

I really want to study this subject, Can I study DP by both OR books and by software industry like python ?

Are they the same with differents approach?

Is the DP in OR books the same when you make a interview in software industry (i.e for software developer) ?

$\endgroup$
2
  • $\begingroup$ Yes it's basically the same idea, with maybe different notation and details because of historical developments and needs of different communities (OR, Computer science, etc). You can read more in the research on Sequential Decision modelling/analytics/algorithms by Warren Powell like here: castlelab.princeton.edu/jungle $\endgroup$
    – dhasson
    Commented Apr 18, 2021 at 20:52
  • $\begingroup$ really thank you. I read the web page. . but can you explain me The sequential Decision in a nustell ? $\endgroup$
    – Locker05
    Commented Apr 18, 2021 at 23:30

1 Answer 1

2
$\begingroup$

It's definitely the same idea. You can look at dynamic programming as developing a program to deal with large combinatorial problems, where brute force just isn't efficient. It comes down to finding a program that runs in polynomial time. And just like we like efficient solutions in OR, it's crucial to write efficient code when you are developing mathematical programs. Nowadays, all these solvers do everything so quickly, that you probably end up working with these packages, rather than developing them yourselves.

You said you wanted to learn the subject and despite the above statement, I do reckon it is really useful to learn it, as it as a very useful way of thinking about problems, especially in OR. But then I would definitely start with learning it via OR-books.

A good example from the OR-side, is the n-period economic lot sizing problem. Wagner and Whitin proposed a dynamic program that runs in $O(n^2)$ time, where Wagelmans, Hoesel and Kolen proposed an algorithm that runs in $O(n \log n)$ time and even in $O(n)$ time for the special case where holding costs are equal and nonnegative for every period.

This is a real nice start if you want to learn to think in terms of dynamic programming (you need to learn how to break up complex problems into small subsets of simpler problems and then combining them). For me personally, it really comes down to learn to think in a different way. When you can do that, you can tackle many other problems that suffer from exploding solution spaces (and there are a lot of them in OR!).

ps: the link to the Wagelmans paper (very interesting!)

https://www.researchgate.net/publication/46431739_Economic_Lot_Sizing_An_On_log_n_Algorithm_That_Runs_in_Linear_Time_in_the_Wagner-Whitin_Case

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.