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

181–190 of 210 posts

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

#181

Post by dahart »

WhitneyLand wrote: post #102
eigenket wrote: post #99

Earlier quoted context omitted.

Run time, runtime and run-time are all commonly used for the thing you want to call run time. None are incorrect. https://www.collinsdictionary.com/dictionary/english/runtime

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.

It seems like you’re confusing your favorite term of art for definitions. One listed valid definition of “runtime” is “the amount of time that a program takes to perform a task”, and as such it’s valid to use the word that way in any context. https://www.oxfordlearnersdictionaries.com/us/definition/eng...

Also worth keeping in mind that usage defines what words mean. If a given usage is common, that makes it de-facto correct, and eventually the dictionary will catch up. This one reason why the dictionaries keep adding new definitions.

Since you’re incorrect about the definitions, and since the meaning of the word runtime was correct in the top comment and understood by everyone reading, and never confused in this thread, the context does not matter here in this case.

I’ve learned from a lot of experience being wrong that the problem with trying to police language is you’re almost never right. Words are beautifully fluid and have multiple and surprising meanings. It’s common for people to mistakenly think the meaning they know is the only meaning, and not be aware of the wider history and usage. So, speaking from experience in the role of English pedant, and getting rightly smacked down, be careful or you end up on the wrong side of your corrections.

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

#182

Post by pmart123 »

FwarkALark wrote: post #34
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.

> If would likely take significant research effort to even figure out a way to incorporate the new discoveries into these engines. What? Have you ever used a solver before? The actual APIs exposed to the user are very simple interfaces that should allow swapping out the backend regardless of the complexity. The idea a new algorithm—short of something like "updating the solution to adjust to a change in data"—would no…

The api interface is simple, but the change would impact the code underneath. Since these are branch and bound algorithms, it would really depend on how often the worst runtime complexity case occurred. If it only happened in 2% of use cases, it might not make a huge difference for example.

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

#183

Post by luca3v »

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

They prove a new upper bound to a combinatorial quantity that controls the worst-case running time of an algorithm of Dadush, not an upper bound to the optimal value of a given ILP instance.

If they wanted to see their ideas work in practice, they could implement Dadush's algorithm in light of these new bounds, but this would be unlikely to outperform something like CPLEX or Gurobi with all their heuristics and engineering optimizations developed over decades.

Otherwise, and this is the sense of the quoted sentence, they could go deep into the bowels of CPLEX or Gurobi to see if their ideas could yield some new speed-up on top of all the existing tricks, but this is not something that makes sense for the authors to do, though maybe someone else should.

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

#184

Post by geysersam »

whatever1 wrote: post #42

It’s great result but probably not useful. Similarly to how interior point methods have better theoretical complexity than simplex for LPs, but fine tuned simplex in reality almost always wins.

I never really understood that. Is there a commonly understood "reason" why IP methods are typically slower in practice?

Seems going through the interior you'd quicker approach a good solution than when being confined to the boundary. But maybe that difference is less important in high dimensions.

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

#185

Post by geysersam »

spywaregorilla wrote: post #176
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…

> Find a domain space with one archetypal decision that gets solved by many different companies

Interesting. Can you give an example of what kind of decisions you're thinking about?

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

#186

Post by spywaregorilla »

geysersam wrote: post #185
spywaregorilla wrote: post #176

Earlier quoted context omitted.

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…

> Find a domain space with one archetypal decision that gets solved by many different companies Interesting. Can you give an example of what kind of decisions you're thinking about?

any sort of scheduling

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

#187

Post by whatever1 »

geysersam wrote: post #184
whatever1 wrote: post #42

It’s great result but probably not useful. Similarly to how interior point methods have better theoretical complexity than simplex for LPs, but fine tuned simplex in reality almost always wins.

I never really understood that. Is there a commonly understood "reason" why IP methods are typically slower in practice? Seems going through the interior you'd quicker approach a good solution than when being confined to the boundary. But maybe that difference is less important in high dimensions.

Calculating derivatives is the most expensive and numerically challenging operation you do in optimization.

Simplex circumvents these issues by traversing the edges of the polytope.

Pivoting is very cheap and from practice we see that you are afforded a LOT of iterations before even start thinking about interior point methods.

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

#188

Post by 7thaccount »

pfdietz wrote: post #170
7thaccount wrote: post #87

Earlier quoted context omitted.

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

Thanks for the comment. I was thinking more about linear programming and related techniques that mostly came about after the war with Dantzig and when computers could be utilized (I know Kantorovich independently also developed the technique before the war). I went ahead and skimmed some articles on OR in WW2. Cool stuff. Thanks for expanding my knowledge.

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

#189

Post by xpe »

__alexs wrote: post #94
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 open source solvers are a mess of 30 years of PhD students random contributions. It's amazing they work at all. If you can possibly avoid actually implementing anything using them you will.

Can others chime in? To what extent is the above this a fair summary?

I would hope there have been some code reorganizations and maybe even rewrites? Perhaps as the underlying theory advances? Perhaps as the ecosystem of tools borrows from each other?

But I don’t know the state of these solvers. In many ways, the above narrative wouldn’t surprise me. I can be rather harsh (but justifiably so I feel) when evaluating scientific tooling. I worked at one national lab with a “prestigious” reputation that nonetheless seemed to be incapable of blending competent software architecture with its domain area. I’m not saying any ideal solution was reachable; the problem arguably had to do with an overzealous scope combined with budgetary limits and cultural disconnects. Many good people working with a flawed plan seems to me.

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

#190

Post by tylerhou »

eru wrote: post #55
tylerhou wrote: post #41

Earlier quoted context omitted.

ILP is NP-complete.

Yes? We do manage to solve ILP problems in practice quite nicely. In fact, most NP problems that you come across in practice are relatively tractable for most practical instances. Eg for the knapsack problem you have to actually work very hard to get a hard instance in the first place.

It was a response to

> It's surprising how many problems can be formulated as linear optimization.

i.e., all problems in NP (which is most problems you're likely to encounter on a day-to-day basis) can be solved with ILP, and many of them can be solved or well-approximated quickly.

Post reply on HN