stncls

18 hari yang laludiscuss

Oh even if your org has a subscription, the fees are insane. You just don't see them.

Things are slowly changing but I can't wait for this parasitic business model to collapse for good.

stncls

7 bulan yang laludiscuss

> The simplest solution however is to use -mcmodel=large which changes all the relative CALL instructions to absolute JMP.

Makes sense, but in the assembly output just after, there is not a single JMP instruction. Instead, CALL <immediate> is replaced with putting the address in a 64-bit register, then CALL <register>, which makes even more sense. But why mention the JMP thing then? Is it a mistake or am I missing something? (I know some calls are replaced by JMP, but that's done regardless of -mcmodel=large)

stncls

12 bulan yang laludiscuss

I don't know about "best", but I'm very happy with my last few Lenovo ThinkPads (X1 carbon, nano, some T-series). Before that, I had some Asus Zenbook, and everything worked as well. All had 4-15hr batteries, more than I expected in their respective eras. I've heard Dell XPS were good too.

There is no black magic. The only trick is checking the amazing Arch Linux wiki [1]. It will tell you everything you need to know, things like avoiding the recent Intel MIPI webcams (Linux support is coming, but count a couple of years for out-of-the-box).

Regarding Desktop Environments, it depends on your taste. I don't enjoy Gnome, but OSX refugees tend to like it. I've used XFCE, LXDE, LXQt, and recently KDE, and I have only good things to say about all. And tiling DE aficionados are spoiled for choice.

Plus, exchanging low-level code with Windows (wsl2) and OSX (largely posix-compatible) has never been easier. The only remaining issue being if you go down to assembly (Aarch64-vs-x86_64), which only crops up if you depend on proprietary applications.

To summarize, the picture is quite good nowadays, has been for a while, and is only improving. Of course, the one problem is closed-source apps. If you rely on one, document yourself on its quirks. Otherwise, Arch Linux wiki for hw support, and you're golden.

[1] https://wiki.archlinux.org

stncls

tahun laludiscuss

A good chunk of the day-to-day work of "operations research" consulting shops is scheduling.

There is also dedicated software like Timefold, formerly RedHat OptaPlanner [0].

[0] https://timefold.ai/blog/optaplanner-fork

stncls

tahun laludiscuss

You're right, but it's very subtle and complicated.

In theory, the simplex method is not known to be polynomial-time, and it is likely that indeed it is not. Some variants of the simplex method have been proven to take exponential time in some worst cases (Klee-Minty cubes). What solvers implement could be said to be one such variant ("steepest-edge pricing"), but because solvers have tons of heuristics and engineering, and also because they work in floating-point arithmetic... it's difficult to tell for sure.

In practice, the main alternative is interior-point (aka. barrier) methods which, contrary to the simplex method, are polynomial-time in theory. They are usually (but not always) faster, and their advantage tends to increase for larger instances. The problem is that they are converging numerical algorithms, and with floating-point arithmetic they never quite 100% converge. By contrast, the simplex method is a combinatorial algorithm, and the numerical errors it faces should not accumulate. As a result, good solvers perform "crossover" after interior-point methods, to get a numerically clean optimal solution. Crossover is a combinatorial algorithm, like the simplex method. Unlike the simplex method though, crossover is polynomial-time in theory (strongly so, even). However, here, theory and practice diverge a bit, and crossover implementations are essentially simplified simplex methods. As a result, in my opinion, calling iterior-point + crossover polynomial-time would be a stretch.

Still, for large problems, we can expect iterior-point + crossover to be faster than the simplex method, by a factor 2x to 10x.

There is also first-order methods, which are getting much attention lately. However, in my experience, you should only use that if you are willing to tolerate huge constraint violations in the solution, and wildly suboptimal solutions. Their main use case is when other solvers need too much RAM to solve your instance.

stncls

tahun laludiscuss

If this is business critical for you, you may want to switch to a faster solver. Glop is very nice, but it would be reasonable to expect a commercial solver (Gurobi, XPress, COpt) to be 60x faster [1]. By the same measure, the best open source solvers (CLP, HiGHS) are 2-3x faster than Glop.

Actually, the commercial solvers are so fast that I would not be surprised if they solved the IP problem as fast as Glop solves the LP. (Yes, the theory says it is impossible, but in practice it happens.) The cost of a commercial solver is 10k to 50k per license.

[1] ... this 60x number has very high variance depending on the type of problem, but it is not taken out of nowhere, it comes from the Mittelmann LP benchmarks https://plato.asu.edu/ftp/lpopt.html There are also benchmarks for other types of problems, including IP, see the whole list here: https://plato.asu.edu/bench.html

stncls

tahun laludiscuss

> Instead, cryptography needs problems that are hard in the average case, like the RSA problem, the discrete logarithm for elliptic curves, and the shortest vector problem for lattices. We don’t technically know whether these are NP-complete

But we do know that the shortest vector problem is NP-hard (in Linf norm), and so is its decision version [1]. We don't have a reduction in the other direction, but we know that SVP is as-hard-as-NP-complete-or-harder.

This goes against the general argument of the article, but only weakly so, because I think lattice-based systems are less broadly deployed than elliptic curves or factoring (not a crypto person, though).

[1] H. Bennett, "The Complexity of the Shortest Vector Problem.", 2022 https://simons.berkeley.edu/sites/default/files/docs/21271/s...

stncls

tahun laludiscuss

Floating-point is hard, and standards seem like they cater to lawyers rather than devs. But a few things are slightly misleading in the post.

1. It correctly quotes the IEEE754-2008 standard:

> A conforming function shall return results correctly rounded for the applicable rounding direction for all operands in its domain

and even points out that the citation is from "Section 9. *Recommended* operations" (emphasis mine). But then it goes on to describes this as a "*requirement*" of the standard (it is not). This is not just a mistype, the post actually implies that implementations not following this recommendation are wrong:

> [...] none of the major mathematical libraries that are used throughout computing are actually rounding correctly as demanded in any version of IEEE 754 after the original 1985 release.

or:

> [...] ranging from benign disregard for the standard to placing the burden of correctness on the user who should know that the functions are wrong: “It is following the specification people believe it’s following.”

As far as I know, IEEE754 mandates correct rounding for elementary operations and sqrt(), and only for those.

2. All the mentions of 1 ULP in the beginning are a red herring. As the article itself mentions later, the standard never cares about 1 ULP. Some people do care about 1 ULP, just because it is something that can be achieved at a reasonable cost for transcendentals, so why not do it. But not the standard.

3. The author seems to believe that 0.5 ULP would be better than 1 ULP for numerical accuracy reasons:

> I was resounding told that the absolute error in the numbers are too small to be a problem. Frankly, I did not believe this.

I would personally also tell that to the author. But there is a much more important reason why correct rounding would be a tremendous advantage: reproducibility. There is always only one correct rounding. As a consequence, with correct rounding, different implementations return bit-for-bit identical results. The author even mentions falling victim to FP non-reproducibility in another part of the article.

4. This last point is excusable because the article is from 2020, but "solving" the fp32 incorrect-rounding problem by using fp64 is naive (not guaranteed to always work, although it will with high probability) and inefficient. It also does not say what to do for fp64. We can do correct rounding much faster now [1, 2]. So much faster that it is getting really close to non-correctly-rounded, so some libm may one day decide to switch to that.

[1] https://github.com/rutgers-apl/rlibm

[2] https://github.com/taschini/crlibm

stncls

tahun laludiscuss

I'm ready to believe that pipewire is imperfect (although I have personally experienced no crash, and did not have to configure anything), but the sentence from the original post is:

> Therefore, I naturally omit the use and configuration of additional audio layers in the form of a Jack server, PulseAudio or the unfortunate PipeWire from RedHat.

I cannot understand this sentiment. I have used all three for years each. If I had to qualify one as "unfortunate", it would certainly not be PipeWire (nor would it be Jack for that matter).

> performance is not that great compared to pulseaudio and jack ..

Jack makes different trade-offs by default, so for some definition of performance, yes, one could see it as superior to PipeWire. But in my experience PipeWire is better than PulseAudio on all axes (at least: latency, CPU usage, resampling quality).

stncls

tahun laludiscuss

> Complexity

> We present a polynomial-time algorithm achieving an approximation ratio below √2 for MVC, providing strong evidence that P = NP by efficiently solving a computationally hard problem with near-optimal solutions.

> This result contradicts the Unique Games Conjecture, suggesting that many optimization problems may admit better solutions, revolutionizing theoretical computer science.

Some context: The Unique Games Conjecture (UGC) is a very central unsolved problem in theoretical computer science (TCS), it's open since 2002. It conjectures that, for a series of standard optimization problems including minimum vertex cover, the best known approximation factor (how close you can guarantee to get to optimality with a poly time algorithm) is actually the best possible approximation factor. To disprove the conjecture, one needs a better approximation algorithm for one of those problems. Such an algorithm could be used to solve (to optimality, and in poly time) another set of problems, which are widely believed to be NP-hard. This would not prove P=NP (to be clear: the above quote is not claiming that), but it is true it would revolutionize TCS.

The thing is: this is TCS and theoretical complexity. You cannot disprove UGC with just code. You need a mathematical proof. This is not an indictment of the code which may be very good. But such an enormous claim would require pretty intense scrutiny before it would be accepted as true.

stncls

2 tahun yang laludiscuss

No vulnerability name, no website, concise description, neutral tone, precise list of affected distros (RHEL + derivatives and some EOL Fedoras) and even mention of unaffected distros (current Fedoras), plain admission that no attempt was made to exploit. What a breath of fresh air!

(I am only joking of course. As a recovering academic, I understand that researchers need recognition, and I have no right to throw stones -- glass houses and all. Also, this one is really like regreSSHion's little sibling. Still, easily finding the information I needed made me happy.)

stncls

2 tahun yang laludiscuss

Yes, only RHEL 9 (the current version of RHEL) and its upstreams/downstreams (CentOS Stream 9, Rocky Linux 9, Alma Linux 9,...).

Also affected: Fedora 37, 36 and possibly 35, which are all end-of-life (since December 2023 in the case of Fedora 37).

Not affected: Fedora 38 (also EOL), 39 (maintained) and 40 (current).

stncls

2 tahun yang laludiscuss

So the AI part is because the customers state their problem in plain English? In your experience, do they prefer that rather than a GUI?

Incidentally, what method do you use to solve the problem once the LLM gives you a formulation? Or is the LLM itself tasked with solving the problem directly?

stncls

2 tahun yang laludiscuss

The article is from 2018 and has had interesting discussion here before [1].

My conclusion is: In production, in a datacenter, when code is stable and compute-per-dollar efficiency matters? Yeah, sure, I can believe that swap makes sense.

On a dev machine? Not on mine for sure. If you think swap is a net positive on a dev machine, then try pasting the following (wrong) code in a bash prompt on Linux:

  echo '
  #include <stdlib.h>
  #include <stdio.h>
  #include <string.h>
  
  int main()
  {
    for (int i = 0; ; i++) {
      char *mem = malloc(1 << 30);
      if (mem == NULL)
        return 0;
      memset(mem, 42, 1 << 30);
      printf("%5d GiB\n", i);
    }
  }
  ' | cc -O3 -o crash_my_laptop -x c -
  ./crash_my_laptop

stncls

2 tahun yang laludiscuss

The music is off as well (second half of piece, I can't quite put my finger on it... Brass section may be out of tune?), but that part sounds more like a poor rendition by humans rather than something a computer would do.

stncls

2 tahun yang laludiscuss

In many cases yes. Some single-threaded workloads are very sensitive to e.g. memory latency. They end up spending most of their time with the CPU waiting on a cache-missed memory load to arrive.

Typically, those would be sequential algorithms with large memory needs and very random (think: hash table) memory accesses.

Examples: SAT solvers, anything relying on sparse linear algebra

stncls

2 tahun yang laludiscuss

Tap water. I can't stop marveling at the fact that we have (mostly) unlimited, clean, drinkable water on demand and virtually for free.

But also many other things, many of which others have mentioned here (cars, mass housing, garbage collection, electronics).

So much so that I feel frustration at the fact that in my job, I do not participate in human society making any of these fascinating things possible; and I have decided that my next career move will have to make me part of the supply chain of one such thing, even if I am just the tiniest of links.

stncls

3 tahun yang laludiscuss

I would answer "yes" to all your questions.

> Was there a major theoretical development in the solver field that allowed this to happen ?

A few major theoretical developments did happen, although the really big ones are 25+ years ago (see Figure 4 in the OP): 5x in 1994 with the incorporation of the dual simplex method, 10x in 1998, mostly because of cutting planes, Gomory cuts specifically.

> Or is it a bunch of tiny tuning heuristics ?

Also yes. Bob Bixby, co-founder of CPLEX and Gurobi, describes mixed-integer programming as "a bag of tricks". And of course, there is a whole spectrum between pure theory and heuristic trickery, it's not black-and-white.

> If so, how are those even possible given that the solver is supposed to be a generic tool applicable to a large class of problem ? > Are there problems whose structure fit a recognizable pattern where optimizations are possible ?

Yes, plenty! Commercial solver developers have a business to run. Clients got problems, they need to solve them, regardless of the algorithm. The canonical example of problem-structure-detection is knapsack problems. CPLEX and Gurobi both detect when their input is a knapsack, and they then run a completely different algorithm to solve it.

At a smaller scale (but larger impact overall), there are a wide range of "presolve" techniques that each detect some microstructures in problems and simplify them [1]. Most of these techniques affect <20% of problems, but together they are extremely powerful.

Another example of half-theoretical half-tricky technique that has a great impact on a few instances by detecting structure: symmetry detection. The theory behind it is serious stuff. Implementing the techniques requires serious (and unpublished) engineering efforts. Most problem instances aren't affected at all. But when it works, you can expect a 10x speedup.

[1] https://opus4.kobv.de/opus4-zib/files/6037/Presolve.pdf

stncls

3 tahun yang laludiscuss

This is precisely what optaplanner was designed to do. Note the optaplanner has been forked by its original author and main contributor when they left RedHat/IBM. The fork is called "TimeFold", most development happens there now.

stncls

3 tahun yang laludiscuss

I agree with grandparent that non-optimal solutions are often enough.

But just to be complete, since TSP was mentioned here:

We could solve TSP instances with >80k cities to optimality back in 2006:

https://www.math.uwaterloo.ca/tsp/

The trick is that some types of problems, like TSP or assignment problems, have structure that can be exploited. Of course they remain NP-hard, so as size grows, at some point the computational cost becomes unsustainable. But the point at which this happens is often way further (i.e. for much larger instances) than most imagine.

Submissions

I built an AI company to save my open source project

Experience writing combinatorics paper in collaboration with LLMs (see Appendix)

Open Source Maintenance

Video ad for World Hearing Day has clear GenAI artifacts [video]

Solver Performance: 1989 vs. 2024

comments