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

61–70 of 210 posts

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

#61

Post by laserbeam »

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…

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 might not even see improvements until you implement an optimized verision of a new algorithm. Even if big O notation says it scales better... The old version may be optimized to use memory efficiently, to make good use of SIMD or other low level techniques. Sometimes getting an optimized implementation of a new algorithm takes time.

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

#62

Post by graycat »

ByteMe95 wrote: post #24
idatum wrote: post #10

Earlier quoted context omitted.

I only recently learned about linear programming. I started with PuLP and Python to get a grasp. It was one of those "How did I miss this??" moments as a developer.

Do you have any recommendations on where to start?

For positive integers m and n, have a m x n matrix A of real numbers. Then also have n x 1 x, 1 x n c, and m x 1 b. Seek x to solve

LP1:

maximize z = cx

subject to

Ax = b

x >= 0

Instead just as easily can do minimize.

Instead of =, might be given >= and/or slack and/or surplus variables to get the problem in the form of LP1.

Any x so that

Ax = b

x >= 0

is feasible. If there is such an x, then LP1 is feasible; else LP1 is infeasible. If LP1 is feasible and for any feasible x we have z bounded above, then LP1 is bounded and has an optimal x (z as large as possible) solution. Else feasible LP1 is unbounded above.

So, LP1 is feasible or not. If feasible, then it is bounded or not. If bounded, then there is at least one optimal solution.

Regard n x 1 x as a point in R^n for the real numbers R.

Cute: If all the numbers in LP1 are rational, then have no need for the reals.

The set of all feasible x is the feasible region and is closed (in the usual topology of R^n) and convex. If LP1 is bounded, then there is at least one optimal x that is an extreme point of the feasible region. So, it is sufficient to look only at the extreme points.

To determine if LP1 is feasible or not, and if feasible bounded or not, and if bounded to find an optimal x, can use the simplex algorithm which is just some carefully selected linear algebra elementary row operations on

z = cx

Ax = b

The iterations of the simplex algorithm have x move from one extreme point to an adjacent one and as good or better on z.

A LOT is well known about LP1 and the simplex algorithm. There is a simpler version for a least cost network flow problem where move from one spanning tree to another.

If insist that the components of x be integers, then are into integer linear programming and the question of P = NP. In practice there is a lot known about ILP, e.g., via G. Nemhauser.

I used to teach LP at Ohio State -- there are lots of polished books from very elementary to quite advanced.

I attacked some practical ILP problems successfully.

I got into ILP (set covering, a darned clever idea since get to handle lots of goofy, highly non-linear constraints, costs, etc. efficiently) for scheduling the fleet at FedEx. The head guy at FedEx wrote me a memo making that problem my work -- officially I reported to the Senior VP Planning, but for that ILP work in every real sense reported to the head guy. The promised stock was very late, so I went for a Ph.D. and got good at lots of math, including optimization, LP, and ILP, etc.

Conclusion: A career in LP or ILP is a good way to need charity or sleep on the street -- literally, no exaggeration.

For some of what AI is doing or trying to do now, LP/ILP stands to be tough competition, tough to beat. And same for lots more in the now old applied math of optimization. Bring a strong vacuum cleaner to get the thick dust off the best books.

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

#63

Post by bnegreve »

black_puppydog wrote: post #47
hdesh wrote: post #44

Earlier quoted context omitted.

> This paper only has 2 authors. So? I don't get the relevance of the author count.

It's quite easy to go tell other people what they should do with their time. These researchers are in the business of improving algorithms. Implementing them in large industrial (or open source) code bases in a maintainable way -- and then actually maintaining that code -- is a different skillset, a different set of interestes, and as was pointed out, besides the point. Either you believe their results, then be grate…

> Implementing them in large industrial (or open source) code bases in a maintainable way -- and then actually maintaining that code -- is a different skillset, a different set of interestes,

You're making a very general point on how algorithm research and software development are two different things, which is of course true. However OP's question is genuine: a lot of research in OR is very practical, and researchers often hack solvers to demonstrate that whatever idea offers a benefit over existing solving techniques. There are no reason to believe that a good new idea like this one couldn't be demonstrated and incorporated into new solvers quickly (especially given the competition).

So the quoted sentence is indeed a bit mysterious. I think it just meant to avoid comment such as "if it's so good why isn't it used in cplex?".

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

#65

Post by FwarkALark »

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

Why is this exposed to the user? If it isn't exposed to the user, what on earth are you talking about?

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

#67

Post by ubj »

eru wrote: post #53
ubj wrote: post #17

Minor nitpick, but the title of this submission should specify "Integer Linear Programming", since the integer part is a much bigger deal. Polynomial time algorithms have been known for linear programming for decades; _integer_ linear programming is NP-hard.

You are right that integer linear programming is NP-hard; but faster algorithms for continuous linear programming are also super interesting and impactful. Continuous linear programming is also _hard_. Not in the sense of NP-hard, but in the sense of there being lots of algorithmic and engineering aspects that go into an efficient, modern LP solver. Even just the numerics are complicated enough. (And many integer lin…

True, these are all fair points! I didn't intend to diminish the impact or complexity of linear programming solvers. Well-written solvers are some of the most useful and powerful computational tools that exist today.

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

#68

Post by yau8edq12i »

andrewp123 wrote: post #66

It seems their result has been out for almost a year now... https://arxiv.org/abs/2303.14605 I'm curious how this affects Traveling Salesman. I was under the impression that all NP-Complete problems take O(n!). Does this method improve it at all?

So what? It takes time for the community to digest the result, grasp its significance, and then write popularization articles about it. If you want to know what's being discovered right this second, read arXiv preprints. If you want to know what was discovered semi-recently and you want an explanation in layman terms that puts the results in perspective, read popularization pieces a while later.

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

#69

Post by blackbear_ »

andrewp123 wrote: post #66

It seems their result has been out for almost a year now... https://arxiv.org/abs/2303.14605 I'm curious how this affects Traveling Salesman. I was under the impression that all NP-Complete problems take O(n!). Does this method improve it at all?

Depending on the problem it can also O(2^n), but that is always the worst case scenario. Modern ILP solvers employ a variety of heuristics that in many cases significantly reduce the time needed to find a solution.

Anecdotally, some years back I was developing MILPs with millions of variables and constraints, and most of them could be solved within minutes to hours. But some of them could not be cracked after weeks, all depending the inputs.

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

#70

Post by mulmboy »

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…

In many cases you can actually insert outside numbers in the middle of the solver process via callbacks. For example see IncumbentUpdater at https://python-mip.readthedocs.io/en/latest/classes.html

And various C APIs for solvers have other callbacks

It's generally quite limited of course, for the reasons you mentioned.

Post reply on HN