Live data from Hacker News

Solver Performance: 1989 vs. 2024

solvermax.com

81–84 of 84 posts

Re: Solver Performance: 1989 vs. 2024

#81
post #24
post #14

Earlier quoted context omitted.

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.

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

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

It's a death sentence for economists, since they rely on every agent optimizing the entire economy of 8 billion agents in real time. 3 hours for 8 million variables isn't real time.

Re: Solver Performance: 1989 vs. 2024

#82
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…

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

Re: Solver Performance: 1989 vs. 2024

#83
post #59

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

It'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), although I am not sure that they can run the full exact same instruction sets.

Re: Solver Performance: 1989 vs. 2024

#84
post #62

Earlier quoted context omitted.

Yes, 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.

> But we should be really happy about the fact that we did not end up in the same place with ML. Why so?

I believe having our tools available as open source is good for the society as a whole.
Post reply on HN