[wenc]

It certainly does look that way for certain classes of problems, as witnessed by the evolution of GPT language models, where the model gets better through sheer use of compute resources.

For many combinatorial problems however, improvements in algorithms can often produce bigger strides than just throwing brute force compute at the problem. Take Mixed Integer Programs (MIPs) -- roughly the optimization-equivalent of SATs -- used for airline scheduling, optimal assignment problems and such. In slide 12 [1] (there are other sources that corroborate), the author notes that MIP solver performance between 1988-2017 had improved 2,527,768,000x.

17,120x was due to machine improvements (single core). 147,650x was due to algorithmic improvements. Multiple cores can also provide a performance boost up to a point, before saturating due to coordination costs. The author notes that "A typical MIP that would have taken 124 years to solve in 1988 will solve in 1 second now".

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.

[1] http://www.focapo-cpc.org/pdf/Linderoth.pdf

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

[mccourt]

Great example of the fact that different circumstances require different approaches, and the fact that brute force is increasingly impractical for combinatorially complex problems. Thanks for this reference.

[dumb1224]

Agree. For classes of problems that human have poor understandings (e.g biology) even better algorithms can not provide better answers. The optimisation might need to happen elsewhere such as re-phrasing the problem or better understanding of related fields (neighbour area). However sample efficiency is indeed very helpful in data deprived area such as biomedical research.

[selimthegrim]

This sounds like the reason Bertsimas at MIT published his new book.