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

61–70 of 84 posts

Re: Solver Performance: 1989 vs. 2024

#61

Post by blt »

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.

Lots of CS theorists are working on non worst case analysis and have been for some time. The CS research community recognizes the limitations of worst case.

It makes sense to teach worst case in undergrad classes because it's easier to understand and basically a prerequisite for other kinds of analysis.

Re: Solver Performance: 1989 vs. 2024

#62

Post by petters »

PartiallyTyped wrote: post #16
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.

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.

Re: Solver Performance: 1989 vs. 2024

#66

Post by baq »

travisjungroth wrote: post #35
baq wrote: post #30

Earlier quoted context omitted.

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…

I'm quite convinced that if you had a 1% better solution to the salesman problem than what fedex or ups currently have, they'll pay good money, though :)

Re: Solver Performance: 1989 vs. 2024

#67

Post by ggouvine »

LunaSea wrote: post #63

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

For mixed integer programming solvers, this thesis is a good reference:

https://opus4.kobv.de/opus4-zib/frontdoor/deliver/index/docI...

Re: Solver Performance: 1989 vs. 2024

#68

Post by sacado2 »

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…

It's often a modeling issue. Modeling languages are so abstract and general they give up a part of the problem's structure.

The most famous example is the pigeonhole problem, when given to SAT solvers. Definition of the problem is: I have n pigeons and m pigeonholes, with n = m + 1. Can I put all n pigeons in a different pigeonhole? The answer is obvious to a human. If I have 20 pigeons and only 19 pigeonholes, I won't make it. But even state of the art SAT solvers will fail at solving this in a reasonable amount of time. Because of the way the problem is represented (a conjunction of boolean clauses). With just a slightly more expressive modeling language (such as pseudo-boolean representation / reasoning), you solve it with the blink of an eye.

We humans are efficient because we recognize the underlying structure of the problem. You'll solve the pigeonhole problem in a split second. But if I encode the problem in CNF (the language of SAT solvers) and give it to you without more information, you won't be able to do it anymore.

Re: Solver Performance: 1989 vs. 2024

#69

Post by adwn »

baq wrote: post #66
travisjungroth wrote: post #35

Earlier quoted context omitted.

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…

I'm quite convinced that if you had a 1% better solution to the salesman problem than what fedex or ups currently have, they'll pay good money, though :)

The problem is that in practice, you don't have complete information, and the information you have is slightly incorrect. You also don't have a complete model, and the model you have is slightly incorrect.

Re: Solver Performance: 1989 vs. 2024

#70

Post by PartiallyTyped »

petters wrote: post #62
PartiallyTyped wrote: post #16

Earlier quoted context omitted.

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

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?

Post reply on HN