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

71–80 of 210 posts

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

#71

Post by aaron695 »

anon291 wrote: post #49
aaron695 wrote: post #18

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

Linear programming on reals is "easy"... You can just check all the points. I believe you can follow the shell of the legal polytope and just use a greedy algorithm to choose the next point that will minimize your goal. If you can get away with a continuous linear program I don't see why you'd use monte carlo. The simplex method will get you an exact answer.

[dead]

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

#72

Post by adrianN »

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?

We actually don't know how long NP-complete problems take to solve. We conjecture that it's superpolynomial, but that can be exponentially faster than O(n!).

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

#73

Post by ubj »

Bimos wrote: post #13

I have a dumb question: how long will it take before this result becoming a pratical MIP solver beating SCIP or gurobi?

Don't forget about the HiGHS solver [1]. MIT licensed and getting to the point where it's outperforming SCIP on the Mittelmann benchmarks [2].

[1]: https://github.com/ERGO-Code/HiGHS

[2]: https://mattmilten.github.io/mittelmann-plots/

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

#74

Post by rocqua »

FwarkALark wrote: post #65
adgjlsfhk1 wrote: post #38

Earlier quoted context omitted.

the interface is simple, but modern solvers apply a ton of heuristics that often dramatically reduce problem size, so a naive implementation of a better algorithm that isn't hooked deeply into the core of an existing ilp solver is likely to be very slow

Why is this exposed to the user? If it isn't exposed to the user, what on earth are you talking about?

From what I gather the parent post is saying that it is easy to make a naive implementation of this improvement, but due to naivety of the implementation it will be slower in practice. Hence it is a lot of work (and thus difficult) to actually put this improvement into practice.

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

#75

Post by imtringued »

math_dandy wrote: post #19
nkh wrote: post #15

For now, the new algorithm hasn’t actually been used to solve any logistical problems, since it would take too much work updating today’s programs to make use of it. But for Rothvoss, that’s beside the point. “It’s about the theoretical understanding of a problem that has fundamental applications,” he said. I don't see how "it would take to much work updating today's programs". Most domain specific models call out to…

The new algorithm of R&R would need to replace the algorithms at the core of Gurobi, CPlex, etc. These tools are marvels of engineering, extremely complex, results of decades of incremental improvements. If would likely take significant research effort to even figure out a way to incorporate the new discoveries into these engines.

These solvers get faster every year, how exactly are they supposed to stay the world's fastest if people invent better algorithms all the time that never get implemented by the commercial offerings?

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

#76

Post by shermantanktop »

axus wrote: post #59
fuzztester wrote: post #54

Earlier quoted context omitted.

How so?

It qualifies you for an opinion on any subject.

A CS degree also qualifies you for on-the-job training in writing code, that odious task that your professors find trivial but somehow are also terrible at it.

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

#77

Post by rocqua »

nkh wrote: post #15

For now, the new algorithm hasn’t actually been used to solve any logistical problems, since it would take too much work updating today’s programs to make use of it. But for Rothvoss, that’s beside the point. “It’s about the theoretical understanding of a problem that has fundamental applications,” he said. I don't see how "it would take to much work updating today's programs". Most domain specific models call out to…

> I don't see how "it would take to much work updating today's programs".

I think some peeps are not reading this sentence the way you meant it to be read.

It seems to me you meant "I don't know what part of this research makes it especially hard to integrate into current solvers (and I would like to understand) ".

But people seem to be interpreting "why didn't they just integrate this into existing solvers? Should be easy (what lazy authors)".

Just trying to clear up some misunderstanding.

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

#78

Post by imtringued »

black_puppydog wrote: post #47
hdesh wrote: post #44

Earlier quoted context omitted.

> This paper only has 2 authors. So? I don't get the relevance of the author count.

It's quite easy to go tell other people what they should do with their time. These researchers are in the business of improving algorithms. Implementing them in large industrial (or open source) code bases in a maintainable way -- and then actually maintaining that code -- is a different skillset, a different set of interestes, and as was pointed out, besides the point. Either you believe their results, then be grate…

>business of improving algorithms

You do realize that the solver companies are in exactly the same boat, right?

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

#79

Post by dang »

mturmon wrote: post #36
dang wrote: post #20

Earlier quoted context omitted.

From that link: Programming in this context does not refer to computer programming, but comes from the use of program by the United States military to refer to proposed training and logistics schedules, which were the problems Dantzig studied at that time Is that also true of 'dynamic programming'?

If you don’t know, you are in for a treat. Here is Bellman’s own description of how he came up with the term “dynamic programming “ — I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman…

Oh gosh—I was vastly out of the loop: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

Thanks! That's a classic for sure.

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

#80

Post by unnah »

nkh wrote: post #22
math_dandy wrote: post #19

Earlier quoted context omitted.

The new algorithm of R&R would need to replace the algorithms at the core of Gurobi, CPlex, etc. These tools are marvels of engineering, extremely complex, results of decades of incremental improvements. If would likely take significant research effort to even figure out a way to incorporate the new discoveries into these engines.

Why would it need to replace them? From the article, they claim they have found a way to reduce the upperbound faster when searching large Integer problems. I don't see how that effects the current searching process. All of these solvers you can enter in an upperbound yourself if you have knowledge of the problem and know a previous solution. So it seems if this is just a programmatic way of reducing the upper bound,…

I don't think they're talking about a bound for the optimum objective value, but a theoretical upper bound for a covering radius related to a convex body and a lattice. The bound would be useful in a lattice-based algorithm for integer linear programming. I don't think there exists an implementation of a lattice algorithm that is practical for non-toy integer linear programming problems, let alone one that is competitive with commercial ILP solvers.
Post reply on HN