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

31–40 of 84 posts

Re: Solver Performance: 1989 vs. 2024

#31

Post by tooltower »

Xcelerate wrote: post #28
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.

> 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 ease. I suspect no, since even a complex but known problem can be solved rather quickly by special-casing.

Re: Solver Performance: 1989 vs. 2024

#32

Post by ur-whale »

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.

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

Re: Solver Performance: 1989 vs. 2024

#34

Post by ur-whale »

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.

Re: Solver Performance: 1989 vs. 2024

#35

Post by travisjungroth »

baq wrote: post #30
ngruhn wrote: post #24

Earlier quoted context omitted.

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…

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

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.

Re: Solver Performance: 1989 vs. 2024

#37

Post by mrloba »

verve_rat wrote: post #29
sp332 wrote: post #18

Earlier quoted context omitted.

Sudoku puzzles are usually set by humans.

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

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

Re: Solver Performance: 1989 vs. 2024

#38

Post by nxobject »

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.

Re: Solver Performance: 1989 vs. 2024

#39

Post by kaba0 »

ur-whale wrote: post #32
codeflo wrote: 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.

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

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.

Re: Solver Performance: 1989 vs. 2024

#40

Post by kaba0 »

foota wrote: post #23
mistercow wrote: post #20

Earlier quoted context omitted.

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

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.

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.
Post reply on HN