[cs702]

> 17,120x was due to machine improvements (single core). 147,650x was due to algorithmic improvements.

That is just... insane. I knew only vaguely that performance had improved significantly for many NP-hard/complete problems in practice, but I did not realize the magnitude of improvement, especially due to better algorithms.

> The biggest improvements in MIP algorithm performance have been due to improvements in solver heuristics (!), because the fastest computations are those that don't have to be performed at all -- i.e. that are eliminated via heuristics.

That is also... remarkable. Thank you for sharing.

I can't help but agree with you :-)

EDIT: Given that most of the "algorithmic" improvements have been due to better solver heuristics, I imagine it should be possible to train meta DL/RL models that learn how to find good heuristics for training DL models with high sample efficiency. Come to think of it, this competition seems to be asking precisely for such "black-box heuristic-guessing" models, so clearly there are people working on it.

[wenc]

Yes, when Bill Bixby (founder of CPLEX and Gurobi, companies that made and still make the fastest MIP solvers in the world) revealed similar numbers a few years ago, many of us practitioners were astounded too.

But those improvements were also a product of lots of smart people funded by cash-rich industries (i.e. oil & gas, airlines... MIPs are big bucks commercially. I recall at one point a commercial CPLEX license was $100k list) poking at the problem for over 30 years. Many Ph.D.s in operations research and mathematical optimization were generated on this topic alone.

[cs702]

Makes sense.

Note that now we have lots of smart people funded by new cash-rich industries (search, social networks, SaaS, etc.) poking at the problem with "black-box" approaches. I will be interesting to see what comes out of it.