# Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems

arXiv: https://arxiv.org/abs/2207.08189 · HTML: https://mlsanity.com/paper/2207.08189/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 53 references that are in the map.
- First posted on arXiv 17 Jul 2022.

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [Normalizing Flows for Probabilistic Modeling and Inference](https://mlsanity.com/paper/1912.02762/) (2019)
- [Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)](https://mlsanity.com/paper/1511.07289/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [A Critical Review of Recurrent Neural Networks for Sequence Learning](https://mlsanity.com/paper/1506.00019/) (2015)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Cyclical Annealing Schedule: A Simple Approach to Mitigating KL Vanishing](https://mlsanity.com/paper/1903.10145/) (2019)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Solving Statistical Mechanics Using Variational Autoregressive Networks](https://mlsanity.com/paper/1809.10606/) (2018)
- [Dilated Recurrent Neural Networks](https://mlsanity.com/paper/1710.02224/) (2017)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Variational Neural Annealing](https://mlsanity.com/paper/2101.10154/) (2021)
- [Training Binary Neural Networks using the Bayesian Learning Rule](https://mlsanity.com/paper/2002.10778/) (2020)
- [Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization](https://mlsanity.com/paper/2011.06188/) (2020)
- [Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning](https://mlsanity.com/paper/2003.00011/) (2020)
- [Many-Qudit representation for the Travelling Salesman Problem Optimisation](https://mlsanity.com/paper/2102.13298/) (2021)
- [Meta Variational Monte Carlo](https://mlsanity.com/paper/2011.10614/) (2020)

## Built on by (most cited first, 6 of 6)

- [Variational Annealing on Graphs for Combinatorial Optimization](https://mlsanity.com/paper/2311.14156/) (2023)
- [Recurrent neural network wave functions for Rydberg atom arrays on kagome lattice](https://mlsanity.com/paper/2405.20384/) (2024)
- [Investigating Topological Order using Recurrent Neural Networks](https://mlsanity.com/paper/2303.11207/) (2023)
- [Nonlocal Monte Carlo via Reinforcement Learning](https://mlsanity.com/paper/2508.10520/) (2025)
- [Geometry-Induced Long-Range Correlations in Recurrent Neural Network Quantum States](https://mlsanity.com/paper/2604.08661/) (2026)
- [Large-scale portfolio optimization with variational neural annealing](https://mlsanity.com/paper/2507.07159/) (2025)

## Abstract (arXiv)

Combinatorial optimization problems can be solved by heuristic algorithms such as simulated annealing (SA) which aims to find the optimal solution within a large search space through thermal fluctuations. The algorithm generates new solutions through Markov-chain Monte Carlo techniques. This sampling scheme can result in severe limitations, such as slow convergence and a tendency to stay within the same local search space at small temperatures. To overcome these shortcomings, we use the variational classical annealing (VCA) framework that combines autoregressive recurrent neural networks (RNNs) with traditional annealing to sample solutions that are uncorrelated. In this paper, we demonstrate the potential of using VCA as an approach to solving real-world optimization problems. We explore VCA's performance in comparison with SA at solving three popular optimization problems: the maximum cut problem (Max-Cut), the nurse scheduling problem (NSP), and the traveling salesman problem (TSP). For all three problems, we find that VCA outperforms SA on average in the asymptotic limit by one or more orders of magnitude in terms of relative error. Interestingly, we reach large system sizes of up to 256 cities for the TSP. We also conclude that in the best case scenario, VCA can serve as a great alternative when SA fails to find the optimal solution.