[HN Gopher] Solver Performance: 1989 vs. 2024
___________________________________________________________________
Solver Performance: 1989 vs. 2024
Author : stncls
Score : 96 points
Date : 2024-01-08 18:43 UTC (4 hours ago)
(HTM) web link (www.solvermax.com)
(TXT) w3m dump (www.solvermax.com)
| datadrivenangel wrote:
| "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 wrote:
| The 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 wrote:
| I'd say on average programmers know less about writing
| optimal code now, but certainly the best in the field know a
| lot more.
| taeric wrote:
| Of 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 wrote:
| 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.
| nwallin wrote:
| 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.
| Epa095 wrote:
| A bit disappointed that there were no reimplementation and real
| benchmarking happening.
| Jtsummers wrote:
| Next 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.
| ngruhn wrote:
| 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.
| dragontamer wrote:
| 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 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.
| azornathogron wrote:
| I do find this interesting...
|
| > Trained Humans are surprisingly good at these problems
|
| Surprising why, and by what metric? (speed? Or quality of
| solution?)
| codeflo wrote:
| A 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.
| azornathogron wrote:
| I was asking about why specifically it's surprising that
| humans are good at such problems. I think that to be
| surprising there must be some prior expectation about how
| good humans should be and then evidence that they're
| actually better than that. Both sides of that are
| interesting and I'd like to know more about it: What is
| the prior expectation of human capabilities here (and
| why), and how does it compare to actual observed
| capabilities.
|
| I'm not sure sudoku is a good example since the problem
| size there is so small that I don't have any intuitive
| sense that it should be something humans can't do.
| cyberax wrote:
| Hmm.... A neural network for register allocation? Might be an
| interesting experiment to try.
| sp332 wrote:
| Sudoku puzzles are usually set by humans.
| verve_rat wrote:
| Not really, as I understand it. The big blow up of sudoku
| books full of puzzles came about because some guy figured
| out how to create them with a program, rather than by hand.
| Earned the guy millions I believe.
|
| Edit: Wayne Gould
| https://en.m.wikipedia.org/wiki/Wayne_Gould
| mrloba wrote:
| People who are more into it usually prefer human made
| puzzles since they often have a logical path that you're
| supposed to find, which can be quite satisfying.
| Generating sudoku puzzles is actually quite easy. Just
| put random numbers on the board until you have a unique
| solution. It runs surprisingly fast. The tricky part is
| deciding on the difficulty. I made a program that would
| identify all the different sudoku techniques needed to
| solve each puzzle (x wings, pairs, all the way up to
| chains), then set the difficulty based on what techniques
| were required. Code is here for anyone interested:
| https://github.com/magnusjt/sudoku/ Sadly I don't think
| anyone would pay millions for this anymore
| mistercow wrote:
| I'm not sure there's necessarily going to be a satisfying
| general answer to find here though. I can invent an NP-
| complete problem with very easy instances by combining a
| linear time problem with an NP-complete problem, e.g. "Does
| this list of cities have a complete route shorter than X OR
| is one of the cities New York?"
|
| All of the "yes New York" solutions are easy, but there's no
| deep, satisfying reason for that. It's just a hard problem
| glued onto an easy problem. For all we know, a lot of NP-hard
| problems could be like that, and the structure of the easy
| instances could be essentially unrelated between problems.
| foota wrote:
| Maybe the answer then is to find what these hard cases are
| and use them in heuristics or approximate algorithms? If we
| could tell when part of the problem is hard, and maybe
| bound the error for them, and use an exact algorithm for
| other parts of the problem, you could get a better result
| in most cases without it blowing up on you.
| kaba0 wrote:
| Well, you can just start an exact solver on the problem
| in one thread, and an approximate algorithm on another.
| If the former doesn't finish in n seconds, you cancel it
| and use the result of the latter.
| kaba0 wrote:
| > 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.
| codeflo wrote:
| 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.
| ngruhn wrote:
| I'm saying this because most people got from their CS degree
| that NP hardness is practically a death sentence. But it's
| really not true. Even if the problem is proven to be NP hard
| (or worse) and every previous approach has failed. There can
| still be some trick or technique (non heuristic!) that brings
| a breakthrough. Maybe you still wait 10^whatever years for a
| solution in some cases. But if you get an answer in seconds
| in 99.9% of cases then its not a big deal in practice.
|
| Even the famous SAT problem can almost be considered solved
| nowadays with the solvers we have.
| fbdab103 wrote:
| It also depends on if you actually need the optimal
| solution. Getting a solution in your time budget, even if
| not guaranteed to be optimal, can be appropriate for many
| problems.
| baq wrote:
| The true benefit of being able to tell NP-complete/NP-hard
| from the garden variety bucket-o-bytes moving is not in
| giving up when you encounter them, as you correctly
| identified, but in knowing that even attempting an optimal
| solution is futile and proceeding to looking for
| approximate solutions to the business problem more or less
| instantly.
|
| People unfamiliar with the matter may attempt to solve the
| problem, might even get rewarded for effort and hard work
| if management is also unfamiliar with the matter. Maybe
| it's fine though...?
| travisjungroth wrote:
| Optimal is overblown for business problems in general.
| Knowing there's a mathematically optimal solution, people
| want it. Even if it's practically impossible to get. It
| feels like if you have the optimal, you don't have to
| consider trade offs (not usually true).
|
| Having a solution within 1% of optimal with ten nines of
| confidence is usually indistinguishable.
|
| Anyone ever notice how these CS problems are rarely
| famous business problems? It's because the pure problems
| don't usually matter and the approximate versions are
| usually quite easy. You almost never need the shortest
| route for a salesman, or need to pick a secretary with no
| chance of going back.
| thechao wrote:
| This reminds me of the random polynomial time bound for the
| simplex algorithm; an algorithm that is, naively, exponential
| time[1].
|
| I seem to vaguely remember -- this is ~17 years ago, now --
| that it's possible to "characterize" the really bad edge-
| cases for simplex and work around them (the whole point of
| the paper).
|
| [1] https://cstheory.stackexchange.com/questions/2373/complex
| ity...
| ur-whale wrote:
| > Solvers can also fail for really tiny problems.
|
| What that tells me is that the current metric we use for
| problem complexity (e.g. big-o) is woefully inadequate at
| measuring the actual complexity of problems.
| kaba0 wrote:
| Why would they be inadequate? They are a very good metric
| that lets one instantly recognize the way the problem's
| certain properties change with respect to some other
| factor. Does it give a complete picture for everything? No.
| Why would it? But to say that they are woefully inadequate
| is just ridiculous.
| TimPC wrote:
| Most instances of a class of problems that are NP-hard are in
| fact easy. Usually NP-hard is something resembling exponential
| blow-up in a problematic edge case.
| Xcelerate wrote:
| > 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 formally, are certain NP-hard problems easier to solve
| because the expected time to solve a randomly selected instance
| from their language is polynomial? Or is it because real-world
| instances are not uniformly distributed across the language,
| and these instances possess some amount of Kolmogorov
| compressibility that leads to better-than-expected performance?
| tooltower wrote:
| 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 ease. I suspect no, since
| even a complex but known problem can be solved rather quickly
| by special-casing.
| Xcelerate wrote:
| > 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
| danbruc wrote:
| 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
| pxn. Don't quote me on the exact numbers, but 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.
| ayhanfuat wrote:
| Sadly, 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 wrote:
| I'm working actively on this area - anyone interested in
| helping should please get in touch! carson@spindle.app
| amluto wrote:
| The 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 wrote:
| The thing is, ML building blocks are very simple and
| composable, I don't think that holds for solvers.
| Chio wrote:
| This is true, but there is HiGHS [1] which is "good enough" to
| use for a lot of real problems (though the commercial solvers
| are still better).
|
| [1] https://highs.dev/
| genman wrote:
| I would side with their grain of salt until they have actually
| completed their promise to implement a crossword puzzle solver
| using integer programming.
| ur-whale wrote:
| 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
| problem ?
|
| Are there problems whose structure fit a recognizable pattern
| where optimizations are possible ?
|
| I confess to being left hanging by the article.
| ngruhn wrote:
| 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 <= 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.
| lowbloodsugar wrote:
| 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.
| nxobject wrote:
| Good catch. That might be a typo: the Prime 750 seems to date
| from 19_7_9.
___________________________________________________________________
(page generated 2024-01-08 23:00 UTC)