[ur-whale]

So solvers are now much faster, but I haven't found a single hint in the article as to how they got faster (aside from the "more memory", "more CPU" aspect).

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.

[ngruhn]

The details are pretty math heavy but what these solvers are doing is they try to find an optimal assignment to a bunch of variables x,y,z,etc while respecting a bunch of constraints like

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.

[stncls]

I would answer "yes" to all your questions.

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

[1] https://opus4.kobv.de/opus4-zib/files/6037/Presolve.pdf