I remember the news articles when Karmarkar's algorithm for linear programming was announced.
Researchers have found a faster way to do integer linear programming
51–60 of 210 posts
Re: Researchers have found a faster way to do integer linear programming
#52Minor nitpick, but the title of this submission should specify "Integer Linear Programming", since the integer part is a much bigger deal. Polynomial time algorithms have been known for linear programming for decades; _integer_ linear programming is NP-hard.
I think we fixed that, albeit by accident when I edited the title earlier. If it needs further fixing let me know!
Re: Researchers have found a faster way to do integer linear programming
#53Minor nitpick, but the title of this submission should specify "Integer Linear Programming", since the integer part is a much bigger deal. Polynomial time algorithms have been known for linear programming for decades; _integer_ linear programming is NP-hard.
You are right that integer linear programming is NP-hard; but faster algorithms for continuous linear programming are also super interesting and impactful.
Continuous linear programming is also _hard_. Not in the sense of NP-hard, but in the sense of there being lots of algorithmic and engineering aspects that go into an efficient, modern LP solver. Even just the numerics are complicated enough.
(And many integer linear programming solvers are based on continuous linear programming solvers.)
Re: Researchers have found a faster way to do integer linear programming
#54Earlier quoted context omitted.
I foresee a future where industrial engineering and CS are combined into some super-degree. There is currently a surprising amount of overlap in the OR side of things, but I'm shocked by how few IE grads can program their way out of a box. It's a shame, really.
CS already is the super-degree.
How so?
Re: Researchers have found a faster way to do integer linear programming
#55Software engineers interested in ML/algorithms should learn about linear programming. It's surprising how many problems can be formulated as linear optimization. For example, in college I was talking to my Industrial Engineer friend about the average minimum number of swaps required to place billiards balls in an acceptable starting position in the rack (triangle). We both happened to write programs that used monte-c…
ILP is NP-complete.
Yes? We do manage to solve ILP problems in practice quite nicely.
In fact, most NP problems that you come across in practice are relatively tractable for most practical instances.
Eg for the knapsack problem you have to actually work very hard to get a hard instance in the first place.
Re: Researchers have found a faster way to do integer linear programming
#56Earlier quoted context omitted.
Do you have any recommendations on where to start?
I wish I can remember how I even learned LP tools existed. I started with this: https://coin-or.github.io/pulp/
The Google OR-tools library is also a good starting point.
I learned about linear programming in uni, but alas I don't think a mathematician's course on linear programming would be a good starting point for practical programmers.
Re: Researchers have found a faster way to do integer linear programming
#57Linear programming is very cool, I loved Vasek Chvatal's book as a kid having accidently bought it thinking it was for computers. But it's tricky to understand and implement and it struggles with real life constraints. i.e. This whole specialty just for integers. Monto Carlo is trivial to understand and implement, adapts to changes and constraints trivially and should be just as good. I'm sure for something high end…
> But it's tricky to understand and implement and it struggles with real life constraints. i.e. This whole specialty just for integers.
Integers are actually harder to deal with than rational numbers in linear programming. Many solvers can also deal with a mixed problem that has both rational and integer variables.
Monte Carlo simulations are an entirely different beast. (Though you probably mean simulated annealing? But that's close enough, I guess. Linear programming is an optimization technique. Monte Carlo by itself doesn't have anything to do with optimization.)
One problem with these other approaches is that you get some answer, but you don't know how good it is. Linear programming solvers either give you the exact answer, or otherwise they can give you a provable upper bound estimate of how far away from the optimal answer you are.
Re: Researchers have found a faster way to do integer linear programming
#58People really need to come up with better names. "Linear Programming" or "Integer Linear Programming" mean absolutely nothing. Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. This is how approximate nearest neighbor works and can still speed up the full solution. Figuring out full paths that have short ave…
Linear programming solvers use lots of heuristics (not entirely unlike the ones you sketched) internally.
The important thing to keep in mind is that their heuristic only speed up the amount of time spent finding the optimal solution. But you still get a prove at the end, that they actually found the optimal solution. (Or if you stop earlier, you get a provable upper bound estimate of how far you are away at worst from the optimal solution.)
Heuristics like the ones you sketched don't (easily) give you those estimates.
Re: Researchers have found a faster way to do integer linear programming
#59Re: Researchers have found a faster way to do integer linear programming
#60Software engineers interested in ML/algorithms should learn about linear programming. It's surprising how many problems can be formulated as linear optimization. For example, in college I was talking to my Industrial Engineer friend about the average minimum number of swaps required to place billiards balls in an acceptable starting position in the rack (triangle). We both happened to write programs that used monte-c…
ILP is NP-complete.
it's not. it's np-hard. the easiest proof is that the best known algorithm is greater than O(2^N)