Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Researchers have found a faster way to do integer linear programming

quantamagazine.org

Post reply on HN
Print view View original

171–180 of 210 posts

Re: Researchers have found a faster way to do integer linear programming

#171

Post by pfdietz »

ur-whale wrote: post #115
mp05 wrote: post #43

Earlier 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.

> but I'm shocked by how few IE grads can program their way out of a box. It's a shame, really. These days, you could replace the "IE" in your sentence by any of many, many disciplines and still be correct. As much as mathematicians will hate to hear this, CS is a new and more tangible/practical way to do maths and should therefore hold a spot in a general education as central as maths has in the last few centuries.

I view mathematics (as in, proving theorems) as one of the professions that's most likely to succumb to automation. We like to think there's some mystical human intuition involved, but that's just us putting things the brain isn't all that good at on a high pedestal.

Re: Researchers have found a faster way to do integer linear programming

#172

Post by duguppy »

I am a little confused about some of the language used here.

> The best version they could come up with — a kind of speed limit — comes from the trivial case where the problem’s variables (such as whether a salesman visits a city or not) can only assume binary values (zero or 1).

Did they just call an NP-Complete problem a trivial case?!

I was under the impression that all ILP can be reduced to 01-ILP equivalents, and vice versa?

> Unfortunately, once the variables take a value beyond just zero and 1, the algorithm’s runtime grows much longer. Researchers have long wondered if they could get closer to the trivial ideal.

So, is the work a solver improving the lower bound for 01-ILP or an algorithm that brings the bounds between 01-ILP and general ILP closer?

Re: Researchers have found a faster way to do integer linear programming

#173

Post by luiwammus »

pfdietz wrote: post #169
luiwammus wrote: post #122

Earlier quoted context omitted.

As other commenters here have mentioned, in discrete optimization there can be a very large gap between efficienct in theory and efficient in practice, and it is very likely that this is the case here too. Linear programming for example is known to be solvable in polynomial time, but the algorithm which does so (the ellipsoid method) is not used in practice because it is prohibitively slow. Instead, people use the (e…

I thought there were other interior point methods now beside the ellipsoid algorithm that performed better. Some of these are useful in convex nonlinear programming, and I believe one is used (with a code generator from Stanford to make it faster) in the guidance software for landing the Falcon 9 first stage. There, as the stage descends it repeatedly solves the problem of reaching the landing point at zero velocity…

Yes, there are other interior point methods besides the ellipsoid method, and virtually all of them perform better for linear programming. Sometimes, the solvers will use these at the root node for very large models, as they can beat out the simplex algorithm. However, I am unsure if any of them has been proven to run in polynomial time, and if so, if the proof is significantly different from the proof for the ellipsoid method. The point I was mainly trying to make is that there can be a significant gap between practice and theory for ILP. Even 40 years after LP was proven to be polytime solvable, simplex remains the most widely used method, and it is very hard for other methods to catch up.

Re: Researchers have found a faster way to do integer linear programming

#174

Post by pfdietz »

luiwammus wrote: post #173
pfdietz wrote: post #169

Earlier quoted context omitted.

I thought there were other interior point methods now beside the ellipsoid algorithm that performed better. Some of these are useful in convex nonlinear programming, and I believe one is used (with a code generator from Stanford to make it faster) in the guidance software for landing the Falcon 9 first stage. There, as the stage descends it repeatedly solves the problem of reaching the landing point at zero velocity…

Yes, there are other interior point methods besides the ellipsoid method, and virtually all of them perform better for linear programming. Sometimes, the solvers will use these at the root node for very large models, as they can beat out the simplex algorithm. However, I am unsure if any of them has been proven to run in polynomial time, and if so, if the proof is significantly different from the proof for the ellips…

Karmarkar's algorithm, for example, has been proved to run in polynomial time.

https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm

It was also (in)famous as an algorithm that was patented (the patent expired in 2006).

Re: Researchers have found a faster way to do integer linear programming

#175

Post by j2kun »

The abstract is more informative: https://arxiv.org/abs/2303.14605

   We obtain a (log(2n))^O(n)-time randomized algorithm to solve integer programs in n variables.
So the work is theoretical: a better exponential-time algorithm than the previous best, based on some analysis of the structure of convex bodies in R^n and how they can be covered by integer grids (lattices).

Most of the practical work on ILPs uses heuristics and branch and bound while taking advantage of the special structure of particular problem formulations. It isn't clear if this work could be used to help either of those, and I imagine without someone from Gurobi (or similar) chiming in, I wouldn't be able to tell from reading the paper.

Re: Researchers have found a faster way to do integer linear programming

#176

Post by spywaregorilla »

sanketskasar wrote: post #136

Can the folks on HN guide me on how to learn and master linear programming and create a consulting career out of it? I've been exposed to linear programming slightly at work and I find this to be powerful technique to solve a lot of problems that are currently written with generic software programming with better results. I feel there is good opportunity to create a consulting career/business out of it, though having…

Don't.

There's a lot of low hanging fruit out there in the world of decisions that get made manually today. If you can do a globally optimal MIP solver, cool, I guess. But often you don't have time to run it, and an immediately calculated and configurable greedy solution is good too. Find a domain space with one archetypal decision that gets solved by many different companies on repeat and just solve that one problem.

The ones that already have software answers are the hard sells.

Re: Researchers have found a faster way to do integer linear programming

#177

Post by j2kun »

andrewp123 wrote: post #66

It seems their result has been out for almost a year now... https://arxiv.org/abs/2303.14605 I'm curious how this affects Traveling Salesman. I was under the impression that all NP-Complete problems take O(n!). Does this method improve it at all?

There is an entire field of research on improving the constants of exponential-time algorithms for NP-hard problems.

Re: Researchers have found a faster way to do integer linear programming

#178

Post by pfdietz »

isaacfung wrote: post #146
eru wrote: post #53

Earlier quoted context omitted.

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 lin…

Yea, Daniel Spielamn and Shang-Hua Teng won the Gödel Prize for their work on smoothed analysis of simplex algorithms. They introduced a way to formally study the worst case complexity of algorithms when the inputs are randomly perturbed by a small amount. https://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf

Spielman in 2013 also (with Adam Marcus and Nikhil Srivastava) came out of left field and solved the long open Kadison-Singer problem, to the surprise of more mainstream mathematicians.

I find this interplay between "traditional" mathematicians and those in allied fields like CS to be very interesting.

Re: Researchers have found a faster way to do integer linear programming

#179

Post by WJW »

PartiallyTyped wrote: post #101
ford wrote: post #4

Software 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…

One of my favourite courses in grad school was approximation algorithms and it involved reductions to LP. Lots of fun, can recommend.

Do you have a link to some materials to help get me started? I did an optimization/ILP MOOC once and that was indeed a lot of fun.
Post reply on HN