8 ms·
Solver Performance: 1989 vs. 2024
- datadrivenangel 3y ago"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.
- dragontamer 3y agoThe software improvements are on an order of 1000x more than the hardware improvements. IE: The software matters more. As in, today's programmers know more about this subject.
- theLiminator 3y agoI'd say on average programmers know less about writing optimal code now, but certainly the best in the field know a lot more.
- owlbite 3y agoI'd say that the algorithm matters more. As in, today's mathematicians know more about the subject. I suspect the actual implementation of said algorithms probably achieves a lower % of peak performance than the older ones (though to be fair they are /much/ more complex algorithms).
- Mr_Minderbinder 3y ago>I suspect the actual implementation of said algorithms probably achieves a lower % of peak performance than the older ones In my experience I have found the opposite to be the case. Most old maths libraries are written in FORTRAN (generally an order of magnitude or more slower than a comparable C/C++) and the implementations of standard algorithms are often sub-optimal and naive. I got the same impression when I compared arctangent (Taylor series) implementations in π programs and Minimax in chess (see Bernstein's program for the 704). I would guess that in the worst case they were 100x slower than what those machines could theoretically achieve. The C+inline asm libraries of today might be 2-10x slower at worst and some are even bottlenecked by memory. In this case I doubt the programs discussed in the 1989 paper, which were written in Prolog and FORTRAN, are exceptions to this.
- taeric 3y agoOf course, it takes knowing how to program to take advantage of the solver improvements. I find that most programs do not, in fact, use any solver techniques. More, I think I can program, but I would also have trouble using solvers in a lot of my programs.
- wiredfool 3y agoI 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.
- nwallin 3y agoMatrix 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.
- wiredfool 3y agoI 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)
- owlbite 3y agoFEAs probably involve sparse matrices, which have a lot more complexity than simple dense matrices. For example compute optimal reordering of a generic sparse matrix is iirc NP-complete.
- hinkley 3y agoThe problem with factorials is that 20 billion doesn't necessarily mean much. Let's say we could solve a problem of 100 elements 35 years ago, with 100! operations. If the 2x10^10 multiplier only made the exact same calculation but faster, that would let you solve n = 105 in the same time. Business problems don't grow that slowly. Not over 35 years. You have to get better at solving the problem in less than n! steps by culling impossible scenarios, and doing it more aggressively.
- Epa095 3y agoA bit disappointed that there were no reimplementation and real benchmarking happening.
- Jtsummers 3y agoNext article apparently. I was very much looking forward to that, too. > In our next article, we'll look to compile crosswords using a MILP model. and > In the next article, we attempt to formulate and solve a MILP to compile crossword puzzles. This is still a difficult problem, though given the improvement in computer and solver speed, there is some basis for optimism that the task is now possible.
- zokier 3y agoExactly. In particular here I suspect the perf is dramatically worse than 1800s/20e9=90ns. Constant factors are real-world annoyance :)
- ngruhn 3y agoThese 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.
- dragontamer 3y agoNP-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 understand something fundamental with regards to NP-hardness. And that's why the research continues, to bring human-like intuition into these problems and provide more automation to these tasks.
- imtringued 3y agoComputers have to solve hard exact problems. You don't seem to understand that heuristics can significantly speed up NP hard problems, especially if you are willing to give up exact solutions.
- azornathogron 3y agoI do find this interesting... > Trained Humans are surprisingly good at these problems Surprising why, and by what metric? (speed? Or quality of solution?)
- codeflo 3y agoA problem is NP hard if there are instances that other hard problems reduce to. That is, only some instances of the problem have to be hard. NP hardness says nothing about "average" problem instances and even less about hand-picked ones. And that's what Sudoku puzzles are. They are made for humans to solve. They are specifically crafted to contain challenging, but possible, solution paths.
- ayhanfuat 3y agoSadly, the field is still mostly dominated by commercial solvers. There are a few open source ones but their performance is nowhere near the commercial ones which is kind of expected given the number of people working on them and the little funding they have. It is really a pity that the OR world hasn't embraced open source as much as ML world.
- crsn 3y agoI'm working actively on this area – anyone interested in helping should please get in touch! carson@spindle.app
- amluto 3y agoThe pricing of some of this software is absurd — easily enough for a company using more than one or two server licenses to dedicate an entire FTE toward open source.
- PartiallyTyped 3y agoThe thing is, ML building blocks are very simple and composable, I don't think that holds for solvers.
- owlbite 3y agoAlso ML gets a lot more funding (academic or commercial) than MILP.
- petters 3y agoYes, I think this is true. I've worked in both fields. But we should be really happy about the fact that we did not end up in the same place with ML.
- PartiallyTyped 3y ago> But we should be really happy about the fact that we did not end up in the same place with ML. Why so?
- genman 3y agoI would side with their grain of salt until they have actually completed their promise to implement a crossword puzzle solver using integer programming.
- SolverMax 3y agoWe did that: https://www.solvermax.com/blog/crossword-milp-model-1 https://www.solvermax.com/blog/crossword-milp-model-1 https://www.solvermax.com/blog/crossword-milp-model-2 https://www.solvermax.com/blog/crossword-milp-model-2 Though note that we're compiling new crosswords, rather than solving existing puzzles.
- ur-whale 3y agoSo 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 problem ? Are there problems whose structure fit a recognizable pattern where optimizations are possible ? I confess to being left hanging by the article.
- ngruhn 3y agoThe 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 <= 10 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.
- stncls 3y agoI 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 https://opus4.kobv.de/opus4-zib/files/6037/Presolve.pdf
- lowbloodsugar 3y ago1989: 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.
- soulbadguy 3y agoAnyone 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
- markwkw 3y agoI wish they tried to solve the 1989 4x4 crossword puzzle optimization with a modern solver, but a small memory limit (~8MB) and perhaps a severely underclocked CPU to showcase the algorithm improvements.
- BizarroLand 3y agoIt's kind of funny because comparable hardware would be hard to find nowadays. Even the ESP32 which can be purchased for something in the neighborhood of $2 runs at 600mips (technically dmips but all that means is they're not benchmarked for floating point operations https://en.wikipedia.org/wiki/ESP32 https://en.wikipedia.org/wiki/ESP32), although I am not sure that they can run the full exact same instruction sets.
- Taikonerd 3y agoI heard about some competition like this: they made a boolean satisfiability problem. Then they ran a "race" -- an old solving algorithm running on modern hardware, versus a new algorithm on old hardware. The new solver won, even with a massive speed handicap!
- LunaSea 3y agoAre there good reference books on solver implementations? I tried diving into the subject using online references but found them lacking in context and explanations sometimes.
- avidphantasm 3y agoYet more reasons to try more central planning rather than rely on analog markets. If it’s good enough for large Capitalist firms, it should be good enough for sectors of the economy.
- 392 3y agoThe map is not the terrain.
- SolverMax 3y agoThanks for your interest in our article about solver performance. We've now posted a follow-up pair of articles where we attempt to compile crossword puzzles using a Mixed Integer Linear Program. Let us know if you have any questions. https://www.solvermax.com/blog/crossword-milp-model-1 https://www.solvermax.com/blog/crossword-milp-model-1 https://www.solvermax.com/blog/crossword-milp-model-2 https://www.solvermax.com/blog/crossword-milp-model-2
- 2toxic 3y agoI wish they put all this increased computer power to solve the real problems, rather than crossword puzzles :/ we may have lived in a 4 day working week already