Hacker News Reader

Comment by wht | Hacker News Reader

In O.R. graduate School, Professor Gene Woolsey told us that he'd rise from the grave and stand on our desks screaming 'No!No!No!' if we ever actually used it to solve a practical problem.

IIRC, his complaints were about the speed of formulation, difficulty to understand and communicate the model to others, and the processing required to regenerate answers when the model changed.

I believe Optiant used Dynamic Programming for supply chain optimization.. So people do or did use it for practical problem solving. ..I think.

View on HN

You might be surpised how far you can get with DP on a modern computer! For example, in https://www.gwern.net/Coin-flip we consider a gambling game with 300 rounds and at least as many options each round, and while it initially sounds infeasible, you can still compute the optimal strategy in under a minute with some optimized C/C++ implementing the DP solution. Modern computers are fast. (And you can define a solution in like 5-10 lines of R/Python if you don't mind them being a lot slower. I don't know how you would solve it with LP or MIP but I suspect it will be both slower and longer.)

What were you supposed to use instead? My impression is that dynamic programming is sometimes sluggish but often better than the alternatives.

Most optimization problems use Linear Programming if the problem has linear/continuous variables and Mixed Integer Programming if binary values (turning something on or off) is part of the solution. These are used in production pretty much everywhere. LP (linear programming) problems are extremely fast too. My company has a HUGE LP & MIP problems and the LPs are still only a few minutes to solve on nice hardware. MIP can be much trickier.

I don't think it's that common to solve, say, shortest paths by solving the LP/MIP formulation (unless maybe the problem at hand isn't strictly a shortest paths problem). Is it?

For something as well known as shortest path, no. One thing about LP/MIP formulations though, is that it's arguably easier to extend. Not to say there aren't tricks to modifying existing algorithms, but most of the time, there is no need to spend all that time, when adding in a few variables or constraints will do the trick for this one problem that you will probably not need to revisit for quite a while.

That's not a drop-in replacement for dynamic programming though, is it? Can you do something like edit distance with IP?

Yea, I'm not familiar with Dynamic Programming, but it sounds different. I'm talking about garden variety optimization problems (minimize or maximize something).

Dynamic Programming is one of the most common tools when doing optimization.

Generally, shortest path algorithms rely on dynamic programming for a reasonable solution. Examples of include the Traveling Salesman.

That's for a certain definition of "optimization problem" right? One could equally say "Most optimization problems use a numerical hill-climbing algorithm".

Unfortunately MIP (and ILP in general), is potentially really really slow, (and proved to me NP-Hard). That extra constraint of a value that must be an integer really complicates things. Still, it's a really nice way to express may optimization problems.

> I believe Optiant used Dynamic Programming for supply chain optimization.. So people do or did use it for practical problem solving. ..I think.

Yes, the least cost path problem is not just a classic DP problem but is an example in this article.

Edit distance (nee Levenshtein distance) is solved with dynamic programming, and is used by spell-checkers.

I agree reformulating the problem can be confusing. It wouldn't be worth it, but for the incredible efficiency gains (not always needed).

Reply on news.ycombinator.com