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

51–60 of 84 posts

Re: Solver Performance: 1989 vs. 2024

#51

Post by jacquesm »

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…

Yes, exactly this. You don't need the optimal solution in most cases, you just need a solution, and if it is 9x% there then the optimum solution can be approximated by burning more cycles but from an economics perspective you may well already have a viable solution in hand.

Re: Solver Performance: 1989 vs. 2024

#52

Post by jacquesm »

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.

> the current metric we use for problem complexity (e.g. big-o) is woefully inadequate at measuring the actual complexity of problems.

The complexity of all problems. But big-O isn't the only complexity metric available.

It's extremely useful and very adequate in almost all cases, but it doesn't work well when the numbers are very small and the problems are part of a small subset of all available problems.

But those are edge cases. In practice those are fairly rare and when the datasets are small enough normally all solutions are more or less viable. But as soon as your data set is non-trivial big-O is the right tool to apply at the outset.

Right tool for the job... small dataset, tricky problem: big-O may not apply.

Re: Solver Performance: 1989 vs. 2024

#53

Post by hinkley »

kaba0 wrote: post #41
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…

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

Our monkey brains can get within a few % of optimal on written TSP problems.

For a lot of these problems, having a tight upper bound lets you narrow the search space, regardless of whether you're looking for the ideal answer or simply a less-bad one (Would you turn down saving $500,000 on fuel and labor in a year just because someone thinks $613,000 is the maximum savings achievable?)

The more we can get automation to do approximations as well as humans, the better.

Re: Solver Performance: 1989 vs. 2024

#54

Post by owlbite »

dragontamer wrote: post #4
datadrivenangel wrote: post #2

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

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.

I'd say that the algorithm matters more. As in, today's mathematicians know more about the subject.

I suspect the actual implementation of said algorithms probably achieves a lower % of peak performance than the older ones (though to be fair they are /much/ more complex algorithms).

Re: Solver Performance: 1989 vs. 2024

#55

Post by owlbite »

nwallin wrote: post #45
wiredfool wrote: post #25

Earlier quoted context omitted.

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.

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.

FEAs probably involve sparse matrices, which have a lot more complexity than simple dense matrices. For example compute optimal reordering of a generic sparse matrix is iirc NP-complete.

Re: Solver Performance: 1989 vs. 2024

#56

Post by owlbite »

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.

Also ML gets a lot more funding (academic or commercial) than MILP.

Re: Solver Performance: 1989 vs. 2024

#57

Post by hinkley »

TimPC wrote: post #22
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.

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.

One of my favorite terms in this space is 'relaxation'.

When you set yourself against the worst case scenario, you are destined to have a very bad time. But there are subsets of the problem where one or two details are treated as trivialities, while still keeping the rest of the problem 'interesting' or 'useful'.

Compression cannot compress white noise. But it turns out humans don't find noise that interesting (except in the negative). We value signal, and meaning. Most of the communication we care to exchange has a much more straightforward message than the medium, and so we continue to find new ways to condense both the message, and the most valuable nuance, down.

Re: Solver Performance: 1989 vs. 2024

#58

Post by hinkley »

datadrivenangel wrote: post #2

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

The problem with factorials is that 20 billion doesn't necessarily mean much.

Let's say we could solve a problem of 100 elements 35 years ago, with 100! operations. If the 2x10^10 multiplier only made the exact same calculation but faster, that would let you solve n = 105 in the same time. Business problems don't grow that slowly. Not over 35 years.

You have to get better at solving the problem in less than n! steps by culling impossible scenarios, and doing it more aggressively.

Re: Solver Performance: 1989 vs. 2024

#60

Post by foota »

kaba0 wrote: post #40
foota wrote: post #23

Earlier quoted context omitted.

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.

The advantage of combining them though is that you might be able to treat different subparts of the problem differently (which is the hard part), so that you could use an approximate algorithm for the hard part of it, and an exact algorithm for the easy part.

Thi of course assumes the problem can be divided in this way, which is fairly speculative.

Post reply on HN