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

131–140 of 210 posts

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

#131

Post by usgroup »

pas wrote: post #33
jcranmer wrote: post #28

Earlier quoted context omitted.

There's been more than a few of these "nature solves NP-hard problems quickly!" kinds of stories, but usually, when one digs deeper, the answer is "nature finds local optima for NP-hard problems quickly!" and the standard response is "so does pretty trivial computer algorithms." In the case of TSP, when you're trying to minimize a TSP with a Euclidean metric (i.e., each node has fixed coordinates, and the cost of the…

https://scottaaronson.blog/?p=266 """ I went to the hardware store, bought some glass plates, liquid soap, etc., and found that, while Nature does often find a minimum Steiner tree with 4 or 5 pegs, it tends to get stuck at local optima with larger numbers of pegs. """

:-) Well, nature also makes you, and you solve problems? So by transitivity ...

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

#132

Post by onetoo »

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.

I don't know much about the specific space of ILP, but speaking more generally...

It is sometimes possible to specialize algorithms and implementations to be faster for certain subdomains of the overall problem, allowing real-world-useful problems to be solved in reasonable time despite the generalized theoretical complexity bound.

If this new algorithm is a fundamentally different approach from the current ones, this may allow ILP to be used in domains where it is currently infeasible. Vice versa, this new algorithm may not be feasible in domains where current tools thrive.

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

#133

Post by muldvarp »

FredPret wrote: post #32
fuidani wrote: post #12

About the travelling salesperson problem, below is a quote from the latest Sapolsky's book Determined: A Science of Life without Free Will. I am not sure how relevant this is for software developers, but still fascinating: "An ant forages for food, checking eight different places. Little ant legs get tired, and ideally the ant visits each site only once, and in the shortest possible path of the 5,040 possible ones (i…

If you try to make your path close to a circle, it’s obviously not guaranteed to be optimal, but it’ll probably be close enough for most small practical applications

You can also just use the Christofides-Serdyukov algorithm. It's fast and it actually has a performance guarantee (it always produces a solution that is at most 1.5 times the length of the optimum).

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

#134

Post by kgwgk »

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.

https://scholar.google.com/scholar?q=“runtime+complexity”

Those references don’t seem to be about environments like Java.

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

#135

Post by iouwhldkfjgklj »

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]

[flagged]

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

#136

Post by sanketskasar »

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 the knowledge and expertise is necessary and there aren't lot of good resources on the internet to learn.

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

#137

Post by aleph_minus_one »

hyperluz wrote: post #125
eigenket wrote: post #111

Earlier quoted context omitted.

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

So, many researchers don't use terms with due care. And many article are rejected by Nature.

> So, many researchers don't use terms with due care. And many article are rejected by Nature.

The reason is much simpler: many (most) researchers are not native English speakers. For example, my doctoral advisor (who knows English well, but is not a native speaker) could hardly help me with questions concerning more subtle aspects of English terms used in the research area. He told me that hardly anybody cares. Even more: when you look for examples, you always have to consider the situation that a word is used wrongly because the author who comes from an arbitrary country does not know better.

Even more: sometimes I do ask native English speakers about subtle aspects of the English language. My impression from this is: while it is not uncommon among native German speakers to deeply analyze German words, various native English speakers independently told me that doing such an analysis "is not how the English language works" (or how native English speakers think about their language).

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

#138

Post by djoldman »

xkcd386 wrote: post #84
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 randomized algorithm that Reis & Rothvoss [1] present at the end of their paper will not be implemented in Gurobi/CPLEX/XPRESS. It remains a fantastic result regardless (see below). But first let me explain. In terms of theoretical computational complexity, the best algorithms for "integer linear programming" [2] (whether the variables are binary or general integers, as in the case tackled by the paper) are based…

Thanks for these resources and comments.

Would say that the following is a good summary? -> This is an important theoretical result, but most real-world problems are far from worst case scenarios, therefore improving the worst case currently has little practical use.

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

#139

Post by 3abiton »

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…

To be fair, I don't see why LP is still being used for many applications nowadays and not replaced, as it tends to be a brute force techniques.

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

#140

Post by davidgrenier »

3abiton wrote: post #139
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…

To be fair, I don't see why LP is still being used for many applications nowadays and not replaced, as it tends to be a brute force techniques.

LP or ILP? There is a significant difference since for non-discrete problem Linear Programming is shockingly efficient and in no way can be considered a brute force technique.

edit: What would be a technique you consider non-brute force in discrete problems?

Post reply on HN