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

121–130 of 210 posts

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

#121

Post by eigenket »

WhitneyLand wrote: post #118
eigenket wrote: post #111

Earlier quoted context omitted.

Fine, I edited "most" in my previous comment to "many". There are still plenty of examples (even on the first page) where the "runtime" is used to mean algorithmic complexity https://arxiv.org/abs/2401.14645 https://arxiv.org/abs/2401.13770 https://arxiv.org/abs/2401.12253 https://arxiv.org/abs/2401.12205 https://arxiv.org/abs/2401.10856

I’ll respond to what I think are the real points: Precision doesn’t matter in this case? I disagree. It was a dick move and pretentious to call it out? Maybe so, it was not my intent and I apologize if it was the case.

My point is that I am a researcher (in quantum information theory) and I've published a couple of papers on quantum computing which talk about algorithmic complexity. In once case I've been told to by an editor to change run time to runtime, and in another case I've been told (by an editor at a different journal) to change run-time to run time.

There isn't a fixed consistent usage, even in the academic literature. More importantly though it doesn't matter which you use, as long as its obvious what you're talking about.

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

#122

Post by luiwammus »

laserbeam wrote: post #61
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…

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 (exponential time worst-case) simplex method.

Modern ILP solvers have a huge number of heuristics and engineering in them, and it is really difficult to beat them in practice after they have optimized their branch-and-cut codes for 30 years. As the top comment mentions, the software improvements alone are estimated to have improved the solving time of practical ILP instances by a factor of 870'000 since 1990.

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

#123

Post by muldvarp »

CyberDildonics wrote: post #3

People really need to come up with better names. "Linear Programming" or "Integer Linear Programming" mean absolutely nothing. Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. This is how approximate nearest neighbor works and can still speed up the full solution. Figuring out full paths that have short ave…

> Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that.

That's the "bound" part of "branch-and-bound", so MILP-solvers already do this.

> You can also cluster points knowing you probably don't want to jump from one cluster to another multiple times.

You can incorporate heuristics into the branch-and-bound algorithm, but the goal of MILP-solvers is generally to produce an optimal solution (or at least a solution that is _provably_ within x% of optimality).

If you don't care about optimality and just want a solution that's good enough, I would implement the Christofides–Serdyukov algorithm.

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

#124

Post by hyperluz »

junon wrote: post #100
WhitneyLand wrote: post #98

Earlier quoted context omitted.

[flagged]

Was #1 really worth mentioning...?

For me, it was, because it was informatve and I'm tired of imprecision, terms overloading, ambiguity and indirectnesses.

Take a look at the Rust's crate.io mess, for example, where people misuse "crate" all the time.

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

#125

Post by hyperluz »

eigenket wrote: post #111
WhitneyLand wrote: post #108

Earlier quoted context omitted.

Your 6135 results are ignoring that there are two different usages. I said “run time” relates to algorithmic complexity. That’s one definition. The other definition is also valid in research, as it relates to environments. Like Java. The first result in your query is an example of the second definition. It is not an example showing these are interchangeable.

Fine, I edited "most" in my previous comment to "many". There are still plenty of examples (even on the first page) where the "runtime" is used to mean algorithmic complexity https://arxiv.org/abs/2401.14645 https://arxiv.org/abs/2401.13770 https://arxiv.org/abs/2401.12253 https://arxiv.org/abs/2401.12205 https://arxiv.org/abs/2401.10856

So, many researchers don't use terms with due care. And many article are rejected by Nature.

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

#126

Post by eru »

imtringued wrote: post #81
eru wrote: post #55

Earlier quoted context omitted.

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.

That's not correct. First of all, you can't solve a neoclassical economy using LP, because equilibrium constraints can only be represented as complementarity constraints. You would have to give up on some aspects, like dynamic prices. The linear complementarity problem in itself is NP hard. So you're screwed from the get go, because your problems are now LPCC problems. Good luck finding an LPCC solver. I can confirm…

Huh? Are you replying to the wrong comment? I never made any claims about 'solving a neoclassical economy'.

I'm not quite sure who cares about solving a neoclassical economic model like that?

As you indirectly suggest, neoclassical assumption of the type you suggested are not computationally tractable. So the kind of computations real economic agents actually do are likely to be different. (Whether that flavour of neoclassical economics is still useful after taking this caveat into account, is a different question.)

In any case: yes, not all NP-hard or NP-complete problems are easy to solve in practice. Even worse, many problems widely believed to be neither NP-hard nor NP-complete, like factoring integers or computing discrete logarithms, are also hard for many practical instances. (And they have to be, if cryptography is supposed to work.)

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

#127

Post by eigenket »

hyperluz wrote: post #125
eigenket wrote: post #111

Earlier quoted context omitted.

Fine, I edited "most" in my previous comment to "many". There are still plenty of examples (even on the first page) where the "runtime" is used to mean algorithmic complexity https://arxiv.org/abs/2401.14645 https://arxiv.org/abs/2401.13770 https://arxiv.org/abs/2401.12253 https://arxiv.org/abs/2401.12205 https://arxiv.org/abs/2401.10856

So, many researchers don't use terms with due care. And many article are rejected by Nature.

I don't really get the love for Nature but here is an example that uses "runtime" in this sense in Nature Computational Science

https://www.nature.com/articles/s43588-023-00589-x

Here is one in Nature Physics

https://www.nature.com/articles/s41567-023-02325-8

Here is one in Nature Precedings

https://www.nature.com/articles/npre.2011.5593.1

And here is one in Nature Communications

https://www.nature.com/articles/s41467-023-44008-1

It isn't a matter of a lack of due care - it just really really doesn't matter which term you use as long as your meaning is clear.

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

#128

Post by muldvarp »

gregod wrote: post #50
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…

The Evolutionary Computation Bestiary [1] list a wide variety of animal behavior inspired heuristics. The foreword includes this great disclaimer: "While we personally believe that the literature could do with more mathematics and less marsupials, and that we, as a community, should grow past this metaphor-rich phase in our field’s history (a bit like chemistry outgrew alchemy), please note that this list makes no cl…

The entire field of metaheuristics is in dire need of a shakeup. Many of the newer publications are not actually novel [0, 1, 2, 3, 4, 5], the metaphors used to describe these methods only disguise their inner workings and similarities and differences to existing approaches and shouldn't justify their publication [6, 7]. The set of benchmarks used to verify the excellent performance of these methods is small and biased [8, 9]. The metaphors don't match the given algorithms [10], the given algorithms don't match the implementation [11] and the results don't match the implementation [12].

It's junk science with the goal of increasing the authors citation count. One of the most prolific authors of papers on "bioinspired metaheuristics" (Seyedali Mirjalili) manages to publish several dozens of papers every year, some gathering thousands if not tens of thousands of citations.

[0]: https://doi.org/10.4018/jamc.2010040104

[1]: https://doi.org/10.1016/j.ins.2010.12.006

[2]: https://doi.org/10.1016/j.ins.2014.01.026

[3]: https://doi.org/10.1007/s11721-019-00165-y

[4]: https://doi.org/10.1007/978-3-030-60376-2_10

[5]: https://doi.org/10.1016/j.cor.2022.105747

[6]: https://doi.org/10.1111/itor.12001

[7]: https://doi.org/10.1007/s11721-021-00202-9

[8]: https://doi.org/10.1038/s42256-022-00579-0

[9]: https://doi.org/10.48550/arXiv.2301.01984

[10]: https://doi.org/10.1007/s11047-012-9322-0

[11]: https://doi.org/10.1016/j.eswa.2021.116029

[12]: https://doi.org/10.1111/itor.12443

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

#129

Post by usgroup »

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…

It's noteworthy that you are describing one of the many ways to do a heuristic search. It doesn't mean that the general form of a problem is not NP-hard, just that a good enough solution can be approximated or an optimal search can be made tractable, by adding more information.

This angle was very prominent during the first AI "revolution" wherein casting AI as search problems augmented by human knowledge was in vogue.

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

#130

Post by keithalewis »

7thaccount wrote: post #90
imtringued wrote: post #81

Earlier quoted context omitted.

That's not correct. First of all, you can't solve a neoclassical economy using LP, because equilibrium constraints can only be represented as complementarity constraints. You would have to give up on some aspects, like dynamic prices. The linear complementarity problem in itself is NP hard. So you're screwed from the get go, because your problems are now LPCC problems. Good luck finding an LPCC solver. I can confirm…

Computational economics is a relatively new field where intelligent agents are used with lots of runs instead of general optimization solvers I believe. Pretty nifty. One of my colleagues publishes a good bit on it.

Wassily Leontief and his Nobel Prize would like to have a chat with your colleague.
Post reply on HN