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 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.
Even the famous SAT problem can almost be considered solved nowadays with the solvers we have.
People unfamiliar with the matter may attempt to solve the problem, might even get rewarded for effort and hard work if management is also unfamiliar with the matter. Maybe it's fine though...?
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.
What's the point of the theoretically perfect solution when the travel times are so unpredictable? The truck stops are 3-5 minutes apart on average (according to random reddit comment [0]), 1% of that is 3 seconds. Meanwhile a single missed light (say because some other vehicle was driving slow or UPS driver was guided into non-familiar route) can add more than a minute.
So something like a better way to arrange packages in truck, or better traffic preidiction model, would be much more useful than any TSP improvements.
[0] https://www.reddit.com/r/UPS/comments/89zw0h/how_long_does_o...
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.
I seem to vaguely remember — this is ~17 years ago, now — that it's possible to "characterize" the really bad edge-cases for simplex and work around them (the whole point of the paper).
[1] https://cstheory.stackexchange.com/questions/2373/complexity...
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 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.
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.
That you can construct a pathological case makes something NP hard for an arbitrary case but not for all cases. Compare with QS: it's very fast for most practical cases but you can construct a case where it performs quite bad, much worse than you'd expect given the name. But in practice that isn't all that relevant.
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 formally, are certain NP-hard problems easier to solve because the expected time to solve a randomly selected instance from their language is polynomial? Or is it because real-world instances are not uniformly distributed across the language, and these instances possess some amount of Kolmogorov compressibility that leads to better-than-expected performance?
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.
I’ve only heard of the incompressibility method but don’t know too much about the details: https://core.ac.uk/download/pdf/301634196.pdf
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 understand something fundamental with regards to NP-hardness. And that's why the research continues, to bring human-like intuition into these problems and provide more automation to these tasks.
> Trained Humans are surprisingly good at these problems
Surprising why, and by what metric? (speed? Or quality of solution?)
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'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.
Edit: Wayne Gould https://en.m.wikipedia.org/wiki/Wayne_Gould
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.
Thi of course assumes the problem can be divided in this way, which is fairly speculative.
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 tasks to be scheduled on a timeline and optimize it. Finding the optimum? No chance.
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.
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.
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.