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

31–40 of 210 posts

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

#31

Post by soperj »

npalli wrote: post #29
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…

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…

Wouldn't the "open source ones like SCIP for the small ones." be public by design?

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

#32

Post by FredPret »

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

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

#33

Post by pas »

jcranmer wrote: post #28
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'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. """

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

#34

Post by FwarkALark »

math_dandy wrote: post #19
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 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 not require any sort of research to slot in as an implementation for the existing interface.

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

#35

Post by defrost »

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

"Did he try jiggling it a bit, and then less and less and less?"

( Annealing /s )

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

#36

Post by mturmon »

dang wrote: post #20
ford wrote: post #5

Earlier quoted context omitted.

This made me wonder why it's called programming (since clearly it's not the sense of the word programming most HN'ers are used to). https://en.wikipedia.org/wiki/Mathematical_optimization#Hist...

From that link: Programming in this context does not refer to computer programming, but comes from the use of program by the United States military to refer to proposed training and logistics schedules, which were the problems Dantzig studied at that time Is that also true of 'dynamic programming'?

If you don’t know, you are in for a treat. Here is Bellman’s own description of how he came up with the term “dynamic programming “ —

I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, ‘Where did the name, dynamic programming, come from?’

The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence.

You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose?

In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense.

It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities (Autobiography, p. 159).

See: https://pubsonline.informs.org/doi/pdf/10.1287/opre.50.1.48....

People up-thread have been getting cranky about the use of “programming “ in this sense.

Now of course, “programming“ for optimization has been well-entrenched since the 1970s at least. But perhaps Bellman’s story does give some cover to those who feel the word “programming“ has been wrongly appropriated?

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

#37

Post by nkh »

npalli wrote: post #29
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…

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 for updating that value in a current solve.

If this paper were a complementally orthogonal implementation from everything that exists in these solvers today, if it can produce a new upper bound, faster than other techniques, it should be fairly plug and play.

I have an undergrad OR degree, and I have been a practitioner for 18 years in LP/MIP problems. So I understand the current capacities of these solvers, and have familiarity with these problems. However, I and am out of my depth trying to understand the specifics of this paper, and would love to be corrected where I am missing something.

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

#38

Post by adgjlsfhk1 »

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 interface is simple, but modern solvers apply a ton of heuristics that often dramatically reduce problem size, so a naive implementation of a better algorithm that isn't hooked deeply into the core of an existing ilp solver is likely to be very slow

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

#39

Post by [deleted] »

adgjlsfhk1 wrote: post #38
FwarkALark wrote: post #34

Earlier quoted context omitted.

> 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 interface is simple, but modern solvers apply a ton of heuristics that often dramatically reduce problem size, so a naive implementation of a better algorithm that isn't hooked deeply into the core of an existing ilp solver is likely to be very slow

[deleted]

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

#40

Post by adgjlsfhk1 »

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.

compared to the previous bound of n^n, log(n)^n looks pretty good.
Post reply on HN