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

111–120 of 210 posts

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

#111

Post by eigenket »

WhitneyLand wrote: post #108
eigenket wrote: post #105

Earlier quoted context omitted.

Going on arXiv computer science and searching for the string "runtime" returns 6135 results, many of which seem use it in the sense we're talking about here. https://arxiv.org/search/cs?query=runtime&searchtype=all&abs... In any case Quanta Magazine is not a formal academic journal, and neither is hacker news. We're having an informal discussion about a popular science article.

Your 6135 results are ignoring that there are two different usages. I said “run time” relates to algorithmic complexity. That’s one definition. The other definition is also valid in research, as it relates to environments. Like Java. The first result in your query is an example of the second definition. It is not an example showing these are interchangeable.

Fine, I edited "most" in my previous comment to "many". There are still plenty of examples (even on the first page) where the "runtime" is used to mean algorithmic complexity

https://arxiv.org/abs/2401.14645

https://arxiv.org/abs/2401.13770

https://arxiv.org/abs/2401.12253

https://arxiv.org/abs/2401.12205

https://arxiv.org/abs/2401.10856

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

#112

Post by ur-whale »

WhitneyLand wrote: post #98
mzl wrote: post #95

Lowering the algorithmic upper bound for a core NP-complete problem is always extremely interesting. However, this is not necessarily related to improving runtime for practical implementations solving the problem in question. Solvers for mixed integer programming (MIP) use a lot of algorithms in conjunction with loads of heuristics. Building up the library of heuristics and strategies is a crucial part of why the imp…

[flagged]

> Sorry to be pedantic

As always, a guaranteed way to make friends.

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

#113

Post by diegoveralli »

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…

Maybe what they mean is that, despite an asymptotic advantage, the new algorithm performs worse for many use cases than the older ones. This might be due to the many heuristics that solvers apply to make problems tractable as others have mentioned, as well as good old software engineering optimization.

So the work that's required is for someone to take this algorithm and implement it in a way that levels the playing field with the older ones.

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

#114

Post by black_puppydog »

imtringued wrote: post #78
black_puppydog wrote: post #47

Earlier quoted context omitted.

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?

no they're not. they're in the business of making their customers' problems solve fast and well. That's of course strongly related, but it is _not_ the same. An algorithm may well be (and this is what OP might be hinting at) be more elegant and efficient, but execute worse on actually existing hardware.

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

#115

Post by ur-whale »

mp05 wrote: post #43
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…

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.

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

#116

Post by yawgmoth »

raverbashing wrote: post #88
nkh wrote: post #22

Earlier quoted context omitted.

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

Honestly? The search for the 'exactly optimal solution' is way overrated I think you can get a moderately efficient solution using heuristics at 1/10 of the time or less Not to mention developer time and trying to figure out which constraints make your problem infeasible. Especially as they get more complicated because you want to make everything linear

I agree, especially when considering that a model is also not reality.

However, what folks often do is find a Linear Solution quickly, then optimize on the Integer Solution, which gives you a gap that you can use to choose termination.

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

#117

Post by muldvarp »

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?

> I was under the impression that all NP-Complete problems take O(n!).

SAT is NP-complete and the naive algorithm ("just try every combination") is O(2^n). Even for TSP there is a dynamic programming approach that takes O(n^2*2^n) instead of O(n!).

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

#118

Post by WhitneyLand »

eigenket wrote: post #111
WhitneyLand wrote: post #108

Earlier quoted context omitted.

Your 6135 results are ignoring that there are two different usages. I said “run time” relates to algorithmic complexity. That’s one definition. The other definition is also valid in research, as it relates to environments. Like Java. The first result in your query is an example of the second definition. It is not an example showing these are interchangeable.

Fine, I edited "most" in my previous comment to "many". There are still plenty of examples (even on the first page) where the "runtime" is used to mean algorithmic complexity https://arxiv.org/abs/2401.14645 https://arxiv.org/abs/2401.13770 https://arxiv.org/abs/2401.12253 https://arxiv.org/abs/2401.12205 https://arxiv.org/abs/2401.10856

I’ll respond to what I think are the real points:

Precision doesn’t matter in this case? I disagree.

It was a dick move and pretentious to call it out?

Maybe so, it was not my intent and I apologize if it was the case.

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

#119

Post by muldvarp »

coliveira wrote: post #30

While this is an interesting theoretical result, we need to remember that they found an algorithm that is (log n)^O(n). In other words, this is not practical to solve problems with moderate to large size n.

> In other words, this is not practical to solve problems with moderate to large size n.

This depends entirely on your definition of "moderate to large". Many real world problems can be solved easily using existing MILP solvers. We will likely never find an algorithm that can solve arbitrarily large instances of NP-complete problems in practice. Heck, it's easy to generate lists that are to large to be sorted with O(n^2) bubblesort.

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

#120

Post by chuckSu »

WhitneyLand wrote: post #98
mzl wrote: post #95

Lowering the algorithmic upper bound for a core NP-complete problem is always extremely interesting. However, this is not necessarily related to improving runtime for practical implementations solving the problem in question. Solvers for mixed integer programming (MIP) use a lot of algorithms in conjunction with loads of heuristics. Building up the library of heuristics and strategies is a crucial part of why the imp…

[flagged]

[dead]
Post reply on HN