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

161–170 of 210 posts

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

#161

Post by pxx »

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]

If you're going to be pedantic, you need to at least be correct. There is no such thing as an "NP class algorithm".

There are, instead, languages that are NP-complete, for which we hypothesize that there are no polynomial-time algorithms for, because that would imply P=NP. It's a further unproven hypothesis that NP-complete languages have no sub-exponential time algorithms (the "exponential time hypothesis").

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

#162

Post by vacuity »

GaryNumanVevo wrote: post #109
WhitneyLand wrote: post #102

Earlier quoted context omitted.

Informally they are used interchangeably. However, their definitions are different. The subject here, is academic research involving algorithmic complexity. What papers do you know of that refer to algorithmic complexity and “runtime”? Context matters. It is incorrect in this context.

Keeping the HN tradition of "pedantry at all costs" alive, I applaud you

You shouldn't be using a comma in that position! You could use a period or semicolon instead!!! How can an esteemed HNer not know basic punctuation?!

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

#165

Post by cvoss »

davidgrenier wrote: post #143

Correct me if I'm wrong but (log n)^O(n) sounds like atrocious complexity?

It is atrocious. It's worse than exponential.

But it's much better than the prior state of the art which was n^n 2^O(n). [1]

The Quanta article, unfortunately, doesn't bother to report the prior complexity for comparison, despite that that's probably the single most important thing to say in order to support the claim in the article's sub-headline.

[1] https://en.m.wikipedia.org/wiki/Integer_programming#Exact_al...

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

#166

Post by tornadofart »

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…

There are algorithms called ant colony optimization https://en.wikipedia.org/wiki/Ant_colony_optimization_algori.... They are modeled after this ant colony behavior. As others have mentioned, these are good at finding local optima, like tabu search or simulated annealing, or genetic algorithms. This is good enough for most business purposes, such as the 'couch production' case from the article and other business cases. However it is not the same as finding 'a general solution'. Sapolsky compares us being bad at finding 'a general solution' with ants capable of finding a local optimum. I find this a bit misleading.

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

#167

Post by christina97 »

hn_throwaway_99 wrote: post #158
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.

> results of decades of incremental improvements. Gurobi was only founded in 2008. I don't doubt the optimizer was the result of "decades of incremental improvements", but the actual implementation must have been started relatively recently.

It was founded by some of the key people behind CPLEX (another solver, founded in 1987). In fact, one of the cofounders of Gurobi was a cofounder of CPLEX prior. They brought decades of knowledge with them.

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

#168

Post by doktrin »

aleph_minus_one wrote: post #137
hyperluz wrote: post #125

Earlier quoted context omitted.

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…

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

I'm tempted to question this idea that English speakers are just unconcerned with their own language, but then I'm not entirely sure what you have in mind when you speak of "deep [linguistic] analysis" (or a lack thereof). Can you provide an example?

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

#169

Post by pfdietz »

luiwammus wrote: post #122
laserbeam wrote: post #61

Earlier quoted context omitted.

I honestly think that's just journalism for "no one implemented it in production yet". Which is not surprising, for an algorithm less than a year old. I don't think it's worth expanding and explaining "too much work". That being said, sometimes if an algorithm isn't the fastest but it's fast and cheap enough, it is hard to argue to spend money on replacing it. Which just means that will happen later. Furthermore, you…

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 with minimum fuel use, subject to various constraints.

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

#170

Post by pfdietz »

7thaccount wrote: post #87
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.

Operations Research is basically Industrial Engineering + Mathematical Optimization + programming familiarity. It's super useful.

I mean, it helped win WW2, so I think its utility is already demonstrated. :)
Post reply on HN