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

11–20 of 84 posts

Re: Solver Performance: 1989 vs. 2024

#11

Post by azornathogron »

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…

I do find this interesting...

> Trained Humans are surprisingly good at these problems

Surprising why, and by what metric? (speed? Or quality of solution?)

Re: Solver Performance: 1989 vs. 2024

#12

Post by crsn »

ayhanfuat wrote: post #9

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.

I'm working actively on this area – anyone interested in helping should please get in touch! carson@spindle.app

Re: Solver Performance: 1989 vs. 2024

#13

Post by codeflo »

azornathogron wrote: post #11
dragontamer wrote: post #8

Earlier quoted context omitted.

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…

I do find this interesting... > Trained Humans are surprisingly good at these problems Surprising why, and by what metric? (speed? Or quality of solution?)

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.

Re: Solver Performance: 1989 vs. 2024

#14

Post by codeflo »

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.

Re: Solver Performance: 1989 vs. 2024

#15

Post by amluto »

ayhanfuat wrote: post #9

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.

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.

Re: Solver Performance: 1989 vs. 2024

#16

Post by PartiallyTyped »

ayhanfuat wrote: post #9

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.

The thing is, ML building blocks are very simple and composable, I don't think that holds for solvers.

Re: Solver Performance: 1989 vs. 2024

#17

Post by cyberax »

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…

Hmm.... A neural network for register allocation? Might be an interesting experiment to try.

Re: Solver Performance: 1989 vs. 2024

#18

Post by sp332 »

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…

Sudoku puzzles are usually set by humans.

Re: Solver Performance: 1989 vs. 2024

#19

Post by azornathogron »

codeflo wrote: post #13
azornathogron wrote: post #11

Earlier quoted context omitted.

I do find this interesting... > Trained Humans are surprisingly good at these problems Surprising why, and by what metric? (speed? Or quality of solution?)

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.

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.

Re: Solver Performance: 1989 vs. 2024

#20

Post by mistercow »

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…

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.

Post reply on HN