# The Solvers Refuse to Die: Classical Optimization vs the Learned Upstarts

> An honest scoreboard of classical optimization solvers versus learning-to-optimize, and the hybrid pattern where ML proposes and exact methods verify.

- Author: Shawn Ng (https://shawnng.com/about)
- Published: 2026-06-06
- Updated: 2026-09-30
- Canonical URL: https://shawnng.com/posts/optimization-classical-vs-learned
- Topics: optimization, operations-research, machine-learning, algorithms, linear-programming

## Key takeaways

- Commercial MIP solvers got roughly 470,000 times faster algorithmically between 1991 and 2012, before counting any hardware gains.
- Exact solvers hand you an optimality certificate, a proof that no better solution exists, which no neural network can produce.
- Learned methods win at fast approximate answers, warm starts, and replacing the hand-tuned heuristics inside exact frameworks.
- They lose badly on optimality certificates, hard constraint feasibility, and out-of-distribution instances, where the algebra simply does not care.
- The pattern that keeps working is hybrid: the learned component supplies intuition about where to search, the classical component supplies guarantees.

In 2021, Google published a Nature paper claiming a reinforcement learning agent could floorplan a TPU chip in six hours, doing work that took human engineers months. It was the flagship result for a movement: neural networks were coming for combinatorial optimization, and the 70-year-old machinery of simplex tableaus and branch-and-bound trees was finally going to be retired. Two years later, an independent team re-ran the comparison at ISPD 2023 and found that simulated annealing (an algorithm from 1983 that any undergraduate can implement in an afternoon) beat the RL agent on the benchmarks they could reproduce. Nature attached an editorial note to the paper. The fight over what AlphaChip actually achieved is still going.

I have spent enough years shipping both kinds of systems to find this fight clarifying rather than embarrassing. It tells you exactly where the boundary sits between what learned methods do well and what they do not, and the boundary is not where either camp's marketing says it is.

## What the Classical Stack Actually Is

When people say "traditional optimization," they usually mean a stack that looks like this, bottom to top.

At the base sits **linear programming**. [Dantzig's simplex method](https://shawnng.com/posts/linear-programming-routes-the-world) (1947) walks the corners of the feasible polytope; Karmarkar's interior-point methods (1984) cut through the middle. Modern solvers carry both and choose per-problem: simplex for warm-startable re-solves, barrier for the enormous ones. LPs with millions of variables solve in seconds. This is a solved problem in the engineering sense: the frontier moved to numerical robustness and presolve tricks decades ago.

On top of LP sits **mixed-integer programming (MIP)**: the same problem, except some variables must take integer values. Assign this crew to this flight or don't. Open this warehouse or don't. MIP is NP-hard, and the standard attack is **branch-and-bound**: solve the LP relaxation, pick a variable with a fractional value, split the problem into two subproblems (variable rounded down, variable rounded up), and recurse, pruning any branch whose LP bound is already worse than the best integer solution found so far. Add cutting planes that tighten the relaxation at each node and you get **branch-and-cut**, which is what Gurobi, CPLEX, and their open-source cousins (SCIP, HiGHS) actually run.

The commercial solvers are absurdly good and getting better. Bob Bixby's longitudinal studies of CPLEX and Gurobi found machine-independent algorithmic speedups of more than **29,000x from 1991 to 2009**, then another 16.2x across Gurobi releases through 2012: roughly **470,000-fold** in two decades, from improvements in presolve, cuts, heuristics, and branching rules, before you count a single transistor of Moore's law. A MIP that was hopeless in 1995 is a rounding error today.

And critically, these solvers give you something no neural network gives you: an **optimality certificate**. When Gurobi terminates with a 0.0% gap, it is not saying "this solution looks good." It is handing you a mathematical proof (a dual bound) that no better solution exists. When it terminates at a 1% gap, it proves your solution is within 1% of whatever the unknown optimum is. If you are dispatching a power grid or scheduling $100M of airline crew, that certificate is the product.

Then there is the honest bottom shelf: **metaheuristics**. Simulated annealing (Kirkpatrick, Gelatt, and Vecchi, 1983; lifted straight from statistical mechanics, complete with a temperature schedule), genetic algorithms, tabu search, large neighborhood search. No guarantees, no certificates, just "perturb the solution, accept improvements, sometimes accept regressions so you don't get stuck." They are the honest choice when your problem is so nonconvex, so black-box, or so riddled with non-mathematical constraints that you cannot write it down as a MIP, or when a good-enough answer in 100 milliseconds beats a provably optimal one in an hour. The best vehicle-routing systems in production are metaheuristics with LP-based components, not the other way around.

## Gradient Descent Won the Biggest Optimization Prize While Nobody Was Looking

Here is the irony the "classical vs new wave" framing misses: the workhorse of all of modern machine learning is *itself* an antique. Cauchy described gradient descent in **1847**. Take the derivative, step downhill:

```
x_{t+1} = x_t - η ∇f(x_t)
```

For 150 years it was a footnote in numerical analysis, dominated for serious work by Newton and quasi-Newton methods with their quadratic convergence. Then [deep learning](https://shawnng.com/posts/how-machines-learned-to-see) arrived with a problem shape the classical toolbox hates: hundreds of billions of parameters (a Hessian is unthinkable), a nonconvex loss surface (no certificates possible even in principle), and (the crucial part) an objective you can only ever evaluate on a minibatch, so every gradient is noisy anyway. Under those conditions, the dumbest first-order method is the right one, and stochastic gradient descent quietly became the most economically consequential optimization algorithm on Earth.

Adam (Kingma and Ba, 2014) is what most people actually run, and it is worth knowing what it really does, because it is simpler than its reputation:

```
m_t = β1·m_{t-1} + (1-β1)·g_t          # EMA of gradients (momentum)
v_t = β2·v_{t-1} + (1-β2)·g_t²         # EMA of squared gradients
x_t = x_{t-1} - η · m̂_t / (√v̂_t + ε)  # per-parameter adaptive step
```

Two exponential moving averages and a division. Each parameter gets its own effective learning rate, scaled inversely to the recent magnitude of its gradients: parameters with small, rare gradients take big steps; parameters with large, noisy gradients take small ones. That is the whole trick, and Adam and its variants train most large language models. So when we ask whether "learned methods" will replace "classical optimization," keep in mind that the learned methods are built *on top of* a classical optimizer from before the telegraph.

## The New Wave: Learning to Optimize

The interesting new work does not try to replace solvers wholesale. It attacks the parts of solvers that were always heuristic anyway.

**Learned branching.** Inside branch-and-bound, the single most consequential decision is which fractional variable to branch on. The gold-standard rule, *strong branching*, actually solves the child LPs for every candidate before choosing: extremely accurate, extremely expensive. Solvers instead use cheap approximations (pseudocost branching) tuned by decades of folklore. Gasse et al. (NeurIPS 2019) trained a graph neural network on the bipartite variable-constraint graph to *imitate* strong branching at pseudocost prices, and it generally solved set covering, auction, and facility location instances faster than SCIP's default, with smaller search trees on the harder set covering and auction instances. This line of work is real: the NeurIPS ML4CO competitions institutionalized it, and both Gurobi and open-source solvers now ship or experiment with ML-tuned heuristics for branching, node selection, and cut selection. Note what the learned component does here: it makes decisions *inside* a framework whose correctness does not depend on those decisions being good. A bad branching choice costs time, never correctness. That is the perfect home for a neural network.

**RL for combinatorial optimization.** The bolder claim is end-to-end: feed the problem instance to a network, get a solution out. Neural TSP solvers are the canonical example: pointer networks (Vinyals, 2015), then attention models trained with REINFORCE (Kool et al., 2018) reaching optimality gaps of about 4.5% on random 100-city instances in under a millisecond each, or 2.3% when sampling 1,280 candidate tours. Impressive, until you meet the incumbents. **Concorde** solves those same 100-city instances to *proven optimality* in well under a second, and in 2006 solved an 85,900-city instance (pla85900) to proven optimality. **LKH-3**, the dominant heuristic, routinely lands within a small fraction of a percent on instances with millions of cities. Meanwhile the neural solvers degrade badly out of distribution: train on uniform random 100-city instances, test on clustered 1,000-city instances, and the gap blows out from a few percent to double digits. On the TSP, the scoreboard is not close, and researchers in the field have been increasingly frank about it.

**Chip floorplanning** is the contested middle ground. Google's 2021 Nature result (now branded AlphaChip) claimed superhuman macro placement and was reportedly used in production TPUs. Cheng, Kahng, and colleagues' ISPD 2023 reproduction found simulated annealing outperforming their reimplementation of the method; Igor Markov published a detailed meta-critique; Google responded that the reproduction under-trained the agent and skipped the pre-training that makes the method work. Nature investigated and let the paper stand with an addendum. My read as an outsider: the result is probably real *inside Google's pipeline, on Google's designs, with Google's pre-training corpus*, and that qualifier is exactly the out-of-distribution fragility problem wearing a corporate badge. A method whose superiority cannot survive contact with an independent benchmark is a method you cannot yet buy.

**Algorithm discovery** is the genuinely new category. AlphaTensor (DeepMind, 2022) framed matrix multiplication as a single-player game and found a way to multiply 4×4 matrices over GF(2) in **47 scalar multiplications**, beating Strassen's 49, which had stood since 1969. AlphaEvolve (2025), an LLM-driven evolutionary search, extended this to 48 multiplications over general complex-valued matrices, and recovered or improved results on dozens of open problems in combinatorics and analysis, including nudging the kissing number bound in 11 dimensions. Notice the structure of these wins: the search is learned, but the *verification* is exact. A candidate matrix multiplication algorithm either computes the right product or it doesn't; checking is mechanical. The AI proposes, arithmetic disposes.

## The Honest Scoreboard

Where learned methods actually win today:

- **Fast approximate solutions under hard latency budgets.** If you need a feasible-ish answer in 10ms and can tolerate 2-5% suboptimality on in-distribution instances (think real-time matching or ranking), a trained policy beats launching a solver. It is the same cheap-first, escalate-when-it-matters shape as [routing work between local models and frontier APIs](https://shawnng.com/posts/local-models-vs-frontier).
- **Warm-starting and primal heuristics.** Predict a good starting solution or partial assignment, hand it to the exact solver, and the branch-and-bound tree shrinks because pruning bounds tighten early. This is free money with no correctness risk.
- **Replacing hand-tuned heuristics inside exact frameworks.** Branching rules, cut selection, node ordering, restart schedules. Decades of expert folklore turn out to be learnable, and often improvable, from data.
- **Search spaces too weird to write down.** Algorithm discovery, architecture search, anywhere the "constraints" are a verifier program rather than linear inequalities.

Where they lose, badly:

- **Optimality certificates.** A neural network cannot prove a bound. Full stop. For regulated, high-stakes, or adversarial settings, this is disqualifying, not a nice-to-have.
- **Constraint feasibility.** A MIP solver treats `x_3 + x_7 ≤ 1` as inviolable law. A neural policy treats it as a strong suggestion. Post-hoc repair of infeasible predictions frequently destroys whatever solution quality the network had, and in problems where feasible solutions are sparse, the network may never find one at all.
- **Out-of-distribution instances.** Solvers do not care that today's problem looks nothing like yesterday's; the algebra is the algebra. Learned solvers can fall apart when instance size, structure, or cost distribution shifts. And in operations, distribution shift is not an edge case, it is Tuesday.
- **The moving target.** The classical stack improved roughly 470,000-fold in two decades and has not stopped. Any learned method benchmarked against last year's solver settings is benchmarked against a corpse.

## The Pattern That Wins: ML Proposes, Exact Methods Verify

Squint at every durable success above and you see the same architecture. The GNN suggests a branching variable; branch-and-bound guarantees the tree search is still exhaustive. The policy network predicts a warm start; the MIP solver certifies the final gap. AlphaTensor dreams up tensor decompositions; exact arithmetic checks each one. AlphaEvolve mutates programs; a verifier scores them. Even AlphaChip, in Google's own telling, sits inside a conventional EDA flow that legalizes and validates its placements.

The learned component supplies **intuition**: a fast, amortized prior over which regions of an exponential space are worth exploring, distilled from thousands of solved instances. The classical component supplies **guarantees**: feasibility, bounds, proofs. Neither can do the other's job. Gradient descent cannot certify; branch-and-bound cannot generalize its search wisdom across instances without a human encoding it as a heuristic. Bolting them together gets you both, and this is not a compromise position; it is what the empirical record has been shouting for five years while both camps argued past each other. Models built to return a typed, calibrated decision instead of text, like [TypeSafe AI's System One model Jev](https://shawnng.com/posts/what-is-jev-system-one-model), are aimed squarely at that proposing role.

The classical stack refuses to die because it was never competing on the axis the new wave attacks. Simplex is not a good heuristic that neural networks can out-guess; it is a proof engine, and proofs do not go out of style. What is dying, quietly and deservedly, is the hand-tuned heuristic: the pseudocost formula from 1971, the branching folklore, the magic constants inside every solver. Those were always just a human's compressed intuition about problem structure, and machines compress intuition better than we do now. The solver of 2030 will still print an optimality certificate at the bottom of its log. It will just have a few dozen neural networks whispering to it about where to look first.

## Frequently asked questions

### Can machine learning replace optimization solvers?

Not for problems that need proofs. A neural network cannot produce an optimality certificate, it treats a hard constraint as a strong suggestion, and it degrades out of distribution. Learned components work best inside an exact framework, where a bad decision costs time but never correctness.

### What is the difference between classical optimization and learning to optimize?

Classical optimization, meaning simplex, branch-and-cut and metaheuristics, searches with algebra and can return bounds you can trust. Learning to optimize trains a model to propose solutions or to guide search decisions. The first gives guarantees, the second gives a fast prior over where to look.

### Do neural networks beat classical solvers on the traveling salesman problem?

No. Attention models trained with REINFORCE reach optimality gaps of about 2% to 4.5% on random 100-city instances, the low end only with heavy sampling, but Concorde solves those same instances to proven optimality in well under a second, and LKH-3 lands within a fraction of a percent on instances with millions of cities.

### What is an optimality certificate?

It is a mathematical proof, in the form of a dual bound, that no better solution exists or that your solution is within a stated gap of the unknown optimum. When a solver terminates at a 0.0% gap that is what it is handing you, and in regulated or high-stakes settings that certificate is the product.

## Sources

- Azalia Mirhoseini, Anna Goldie, et al. (2021). [A graph placement methodology for fast chip design](https://doi.org/10.1038/s41586-021-03544-w). Nature.
- Chung-Kuan Cheng, Andrew B. Kahng, Sayak Kundu, Yucheng Wang, Zhiang Wang (2023). [Assessment of Reinforcement Learning for Macro Placement](https://doi.org/10.1145/3569052.3578926). Proceedings of the 2023 International Symposium on Physical Design (ISPD 2023), ACM.
- Robert E. Bixby (2012). [A Brief History of Linear and Mixed-Integer Programming Computation](https://doi.org/10.4171/dms/6/16). Documenta Mathematica, Extra Volume ISMP.
- Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, Andrea Lodi (2019). [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://arxiv.org/abs/1906.01629). NeurIPS 2019.
- Wouter Kool, Herke van Hoof, Max Welling (2019). [Attention, Learn to Solve Routing Problems!](https://arxiv.org/abs/1803.08475). ICLR 2019.
- M. Benichou, J. M. Gauthier, P. Girodet, G. Hentges, G. Ribière, O. Vincent (1971). [Experiments in mixed-integer linear programming](https://doi.org/10.1007/BF01584074). Mathematical Programming.
- Alhussein Fawzi, Matej Balog, Aja Huang, et al. (2022). [Discovering faster matrix multiplication algorithms with reinforcement learning](https://doi.org/10.1038/s41586-022-05172-4). Nature.