Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solver Performance: 1989 vs. 2024

solvermax.com

Post reply on HN
Print view View original

41–50 of 84 posts

Re: Solver Performance: 1989 vs. 2024

#41

Post by kaba0 »

dragontamer wrote: post #8
ngruhn wrote: post #7

These solvers really show that NP-hardness is no reason to give up. For example, they can solve surprisingly large Traveling Salesmen instances to proven optimality.

NP-hard problems commonly come up as human-solvable puzzles. Like Sudoku... or perhaps a more applicable problem... layout and routing of electronic components on a PCB and/or chip. Or even assembly-language register allocation (coloring and packing problem). Trained Humans are surprisingly good at these problems, far better than expected given how much computational power we have today. So its clear we don't underst…

> Trained Humans are surprisingly good at these problems

Are we? I don’t think we would even start working on problems with big enough `n` where the complexity actually ramps up.

Like, optimally scheduling even just a couple of things will have a shitton of combinations, and I really doubt we would be good at it.

Good at iteratively decreasing a cost function? Yeah, I guess with a good interface we could move around tasks to be scheduled on a timeline and optimize it. Finding the optimum? No chance.

Re: Solver Performance: 1989 vs. 2024

#42

Post by ngruhn »

ur-whale wrote: post #34

So solvers are now much faster, but I haven't found a single hint in the article as to how they got faster (aside from the "more memory", "more CPU" aspect). Was there a major theoretical development in the solver field that allowed this to happen ? Or is it a bunch of tiny tuning heuristics ? If so, how are those even possible given that the solver is supposed to be a generic tool applicable to a large class of prob…

The details are pretty math heavy but what these solvers are doing is they try to find an optimal assignment to a bunch of variables x,y,z,etc while respecting a bunch of constraints like

3x + 2y 4z >= 3.5

Additionally, there is an “objective function” that defines what optimal means. Something like:

maximize (3x + 10y - 2z)

It’s not obvious but all kinds of problems can be modeled in this framework, like scheduling-, graph-, routing- problems. A big application is logistics: maximize profit / minimize costs under certain constraints.

So the solvers are just dealing with this inequality solving business. And this is where a lot of theoretical advances have happened. It’s a large field and I barely scratch the surface but it’s very interesting. Some keywords are: Operations Research, Mixed Integer Programming, Simplex Method.

Re: Solver Performance: 1989 vs. 2024

#43

Post by Xcelerate »

tooltower wrote: post #31
Xcelerate wrote: post #28

Earlier quoted context omitted.

> they can solve surprisingly large Traveling Salesmen instances to proven optimality. For someone who studies computational complexity theory, is the ability to solve some instances of NP-hard problems efficiently due more to these instances having lower average-case complexity than worst-case complexity, or because they possess structural properties that allow for more effective algorithmic exploitation? More forma…

The latter. The real-world instances are not uniformly distributed across the language. It is pretty easy to randomly generate problems that are hard for current solvers. Caveats: * "uniform distribution" is a tricky concept over infinite countable sets. Famously, it doesn't exist. You have to restrict the length or something. * I have no idea if there's a concrete result linking Kolmogorov complexity and solving eas…

> I have no idea if there's a concrete result linking Kolmogorov complexity and solving ease

I’ve only heard of the incompressibility method but don’t know too much about the details: https://core.ac.uk/download/pdf/301634196.pdf

Re: Solver Performance: 1989 vs. 2024

#44

Post by danbruc »

tooltower wrote: post #31
Xcelerate wrote: post #28

Earlier quoted context omitted.

> they can solve surprisingly large Traveling Salesmen instances to proven optimality. For someone who studies computational complexity theory, is the ability to solve some instances of NP-hard problems efficiently due more to these instances having lower average-case complexity than worst-case complexity, or because they possess structural properties that allow for more effective algorithmic exploitation? More forma…

The latter. The real-world instances are not uniformly distributed across the language. It is pretty easy to randomly generate problems that are hard for current solvers. Caveats: * "uniform distribution" is a tricky concept over infinite countable sets. Famously, it doesn't exist. You have to restrict the length or something. * I have no idea if there's a concrete result linking Kolmogorov complexity and solving eas…

I played quite a bit with vertex three coloring in the past and it has a surprisingly sharp phase transition. If you randomly generate graphs by including each possible edge with probability p, then the graph will have average degree p×n. Don't quote me on the exact numbers, but something like if the average degree is about 3, then the graph is usually hard to color. If it is only 2.9, then the graph is usually easy to color, if it is 3.1 then there is usually either no valid coloring at all or it is easy to find one. So of all the graphs with average degree from 0 to n, mostly only graphs with average degree in a narrow band around 3 are hard.

Re: Solver Performance: 1989 vs. 2024

#45

Post by nwallin »

wiredfool wrote: post #25
datadrivenangel wrote: post #2

"Combining the computer hardware speed increase of 4,000 times with the solver software performance improvement of 5 million times, the total improvement from 1989 to 2024 is a factor of 20 billion times faster!" No wonder people have started making jokes that programmers no longer know how to program! We can get away with a lot more now.

I went to a Guest lecture in ~96 on performance of supercomputing and applications to FEA, so basically matrix factoring. In the time from the Cray 1 -> then, there were 6 orders of magnitude of hardware gains, and 6 orders of magnitude in software as well.

Matrix factoring as in LU, Cholesky, QR, SVD etc? 6 orders of magnitude from mid-70s to mid-90s?

Unless I'm misunderstanding I'm shocked that there was that much left on the table.

Re: Solver Performance: 1989 vs. 2024

#46

Post by wiredfool »

nwallin wrote: post #45
wiredfool wrote: post #25

Earlier quoted context omitted.

I went to a Guest lecture in ~96 on performance of supercomputing and applications to FEA, so basically matrix factoring. In the time from the Cray 1 -> then, there were 6 orders of magnitude of hardware gains, and 6 orders of magnitude in software as well.

Matrix factoring as in LU, Cholesky, QR, SVD etc? 6 orders of magnitude from mid-70s to mid-90s? Unless I'm misunderstanding I'm shocked that there was that much left on the table.

I think it went from naïve gaussian through LU and SVD to approximate iterative forms for the top eigenvectors/values. So a good portion of that was not computing the higher order terms that didn't significantly contribute to the results.

Hazy memory though, as it was 25 years back and I've been out of the FEA side of things for 20+ years now.

I will say though -- I was doing some stuff at the time that was burying SuperSparcs for 24 hours at a time, and would now probably run realtime on a watch or phone. (Again, a big mix of hardware advancement, reduced precision for insignificant terms, and generally optimized algos)

Re: Solver Performance: 1989 vs. 2024

#47

Post by soulbadguy »

Anyone has a good literature review (or anything similar) on AI technics applied to ILP/constraints solver ?

I have seen a couple of result for specific domain ( like place and route ) but I am wondering how those new technics fair in more general settings

Re: Solver Performance: 1989 vs. 2024

#48

Post by Jtsummers »

nxobject wrote: post #38
lowbloodsugar wrote: post #36

1989: Odd that the superminicomputer that cost hundreds of thousands had 8MB RAM and managed 1 MIPS, while my Acorn Archimedes cost $2000 had 1MB (and you could get up to 4MB) and managed 8 MIPS.

Good catch. That might be a typo: the Prime 750 seems to date from 19_7_9.

The paper was written in 1988 and published in 1989 (1 Jan 1989, so just). The Prime 750 is specifically named in the paper, it was probably the best system he had access to when doing the work.

Re: Solver Performance: 1989 vs. 2024

#49

Post by stncls »

ur-whale wrote: post #34

So solvers are now much faster, but I haven't found a single hint in the article as to how they got faster (aside from the "more memory", "more CPU" aspect). Was there a major theoretical development in the solver field that allowed this to happen ? Or is it a bunch of tiny tuning heuristics ? If so, how are those even possible given that the solver is supposed to be a generic tool applicable to a large class of prob…

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

Re: Solver Performance: 1989 vs. 2024

#50

Post by jacquesm »

codeflo wrote: post #14
ngruhn wrote: post #7

These solvers really show that NP-hardness is no reason to give up. For example, they can solve surprisingly large Traveling Salesmen instances to proven optimality.

Solvers aren't magic. But it turns out that many naturally occurring instances of NP-hard problems aren't the "really hard" instances that the NP-hardness proof depends on. Solvers can also fail for really tiny problems. You simply have to try to figure out how hard (or how well adapted to the solver's heuristics) your particular problem instance is.

NP hard for a pathological case doesn't mean all practical cases are pathological. Many of the cases have optimal solutions in a reasonable amount of time without resorting to brute force because you can use structure in the dataset to limit the search space.

That you can construct a pathological case makes something NP hard for an arbitrary case but not for all cases. Compare with QS: it's very fast for most practical cases but you can construct a case where it performs quite bad, much worse than you'd expect given the name. But in practice that isn't all that relevant.

Post reply on HN