The Old Guard Refuses to Die: Classical Optimization vs the Learned Upstarts

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 (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 on the order of a million-fold between 1991 and the mid-2010s: 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 "old guard 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 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 it trained GPT-4. 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 produced smaller search trees and faster solves than SCIP's default on set covering, auction, and facility location 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 ~1% optimality gaps on random 100-city instances in milliseconds. 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 1% 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.
• 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 a million-fold in 25 years 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.

The old guard 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 1978, 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.