3 ms·

Most optimization problems use Linear Programming if the problem has linear/continuous variables and Mixed Integer Programming if binary values (turning somethi

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.

gugagore 9y ago
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?
- xoroshiro 9y ago
  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.
mattkrause 9y ago
That's not a drop-in replacement for dynamic programming though, is it? Can you do something like edit distance with IP?
- throwaway7645 9y ago
  Yea, I'm not familiar with Dynamic Programming, but it sounds different. I'm talking about garden variety optimization problems (minimize or maximize something).
  - gicadin 9y ago
    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.
Myrmornis 9y ago
That's for a certain definition of "optimization problem" right? One could equally say "Most optimization problems use a numerical hill-climbing algorithm".
hvidgaard 9y ago
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.

gugagore 9y ago

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?

xoroshiro 9y ago
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.

mattkrause 9y ago

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

throwaway7645 9y ago
Yea, I'm not familiar with Dynamic Programming, but it sounds different. I'm talking about garden variety optimization problems (minimize or maximize something).
- gicadin 9y ago
  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.

Myrmornis 9y ago

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

hvidgaard 9y ago

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.