Hacker News Reader

Comment by mattkrause | Hacker News Reader

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

View on HN

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.

Reply on news.ycombinator.com