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

91–100 of 210 posts

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

#91

Post by Aaronmacaron »

nkh wrote: post #37
npalli wrote: post #29

Earlier quoted context omitted.

You seem to be confusing problem formulation with the problem solution. It is true there is a standard way to exchange the problem formulation through something like MPS (though it seems AML's like AMPL etc. have taken over). All this format gives you is a standard mathematical formulation of the problem. However, the solution is something very specific to the individual solver and they have their own data structures…

All these solvers use branch and bound to explore the solution space and "fathom" (i.e. eliminate candidate search trees if the lowest possible value for the tree is above an already found solution). The upper bound that the solver calculates via pre-solve heuristics and other techniques does vary from solver to solver. However, they all have a place for "Upper bound", and there are mechanisms in all of these solvers…

What is OR?

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

#92

Post by aix1 »

Aaronmacaron wrote: post #91
nkh wrote: post #37

Earlier quoted context omitted.

All these solvers use branch and bound to explore the solution space and "fathom" (i.e. eliminate candidate search trees if the lowest possible value for the tree is above an already found solution). The upper bound that the solver calculates via pre-solve heuristics and other techniques does vary from solver to solver. However, they all have a place for "Upper bound", and there are mechanisms in all of these solvers…

What is OR?

Operations Research: https://en.m.wikipedia.org/wiki/Operations_research

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

#93

Post by [deleted] »

Aaronmacaron wrote: post #91
nkh wrote: post #37

Earlier quoted context omitted.

All these solvers use branch and bound to explore the solution space and "fathom" (i.e. eliminate candidate search trees if the lowest possible value for the tree is above an already found solution). The upper bound that the solver calculates via pre-solve heuristics and other techniques does vary from solver to solver. However, they all have a place for "Upper bound", and there are mechanisms in all of these solvers…

What is OR?

[deleted]

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

#94

Post by __alexs »

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.

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

#95

Post by mzl »

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 improvement in MIP solvers have outpaced Moores law. From https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6..., the improvements in hardware from 1990 to 2014 was 6500x. But the improvements to the software are responsible for 870000x performance improvement.

The referenced article may become another part of the puzzle in continuing performance improvements for MIP solvers, but it is not in any way a given.

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

#96

Post by Al-Khwarizmi »

shermantanktop wrote: post #76
axus wrote: post #59

Earlier quoted context omitted.

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.

We just don't have time. Incentives are elsewhere. Any time devoted to writing good code for a paper is time we cannot use to work on the next paper, (shudder) grant application, or a plethora of other things that we are either forced or incentivized to do.

I miss coding from when I was in a more junior stage of my career and could afford time for it, and I think my fellow professors mostly feel the same, I don't think many would dismiss it as trivial or odious.

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

#97

Post by BlindEyeHalo »

tylerhou wrote: post #41
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…

ILP is NP-complete.

Just because it is NP-hard in the worst-case doesn't mean it is not practical. As can be seen in the many theorems under which conditions the regular polynomial-time LP algorithm provides an integer solution.

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

#98

Post by WhitneyLand »

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]

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

#99

Post by eigenket »

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]

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

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

#100

Post by junon »

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]

Was #1 really worth mentioning...?
Post reply on HN