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.
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.
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.
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.
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.
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.
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.
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.
> Trained Humans are surprisingly good at these problems
Surprising why, and by what metric? (speed? Or quality of solution?)
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.
> In our next article, we'll look to compile crosswords using a MILP model.
and
> In the next article, we attempt to formulate and solve a MILP to compile crossword puzzles. This is still a difficult problem, though given the improvement in computer and solver speed, there is some basis for optimism that the task is now possible.
I have seen a couple of result for specific domain ( like place and route ) but I am wondering how those new technics fair in more general settings
No wonder people have started making jokes that programmers no longer know how to program! We can get away with a lot more now.
IE: The software matters more. As in, today's programmers know more about this 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).
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.
Unless I'm misunderstanding I'm shocked that there was that much left on the table.
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.
Even the ESP32 which can be purchased for something in the neighborhood of $2 runs at 600mips (technically dmips but all that means is they're not benchmarked for floating point operations https://en.wikipedia.org/wiki/ESP32), although I am not sure that they can run the full exact same instruction sets.
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.
3x + 2y <= 10
4z >= 3.5
Additionally, there is an “objective function” that defines what optimal means. Something like:
maximize (3x + 10y - 2z)
It’s not obvious but all kinds of problems can be modeled in this framework, like scheduling-, graph-, routing- problems. A big application is logistics: maximize profit / minimize costs under certain constraints.
So the solvers are just dealing with this inequality solving business. And this is where a lot of theoretical advances have happened. It’s a large field and I barely scratch the surface but it’s very interesting. Some keywords are: Operations Research, Mixed Integer Programming, Simplex Method.
> Was there a major theoretical development in the solver field that allowed this to happen ?
A few major theoretical developments did happen, although the really big ones are 25+ years ago (see Figure 4 in the OP): 5x in 1994 with the incorporation of the dual simplex method, 10x in 1998, mostly because of cutting planes, Gomory cuts specifically.
> Or is it a bunch of tiny tuning heuristics ?
Also yes. Bob Bixby, co-founder of CPLEX and Gurobi, describes mixed-integer programming as "a bag of tricks". And of course, there is a whole spectrum between pure theory and heuristic trickery, it's not black-and-white.
> 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 ?
Yes, plenty! Commercial solver developers have a business to run. Clients got problems, they need to solve them, regardless of the algorithm. The canonical example of problem-structure-detection is knapsack problems. CPLEX and Gurobi both detect when their input is a knapsack, and they then run a completely different algorithm to solve it.
At a smaller scale (but larger impact overall), there are a wide range of "presolve" techniques that each detect some microstructures in problems and simplify them [1]. Most of these techniques affect <20% of problems, but together they are extremely powerful.
Another example of half-theoretical half-tricky technique that has a great impact on a few instances by detecting structure: symmetry detection. The theory behind it is serious stuff. Implementing the techniques requires serious (and unpublished) engineering efforts. Most problem instances aren't affected at all. But when it works, you can expect a 10x speedup.
We've now posted a follow-up pair of articles where we attempt to compile crossword puzzles using a Mixed Integer Linear Program.
Let us know if you have any questions.
https://www.solvermax.com/blog/crossword-milp-model-1
https://www.solvermax.com/blog/crossword-milp-model-2
Though note that we're compiling new crosswords, rather than solving existing puzzles.
I tried diving into the subject using online references but found them lacking in context and explanations sometimes.
https://opus4.kobv.de/opus4-zib/frontdoor/deliver/index/docI...
