Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems

Abstract

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.

arXiv comment14 pages, 3 figures, 4 tables. Github code: https://github.com/RNN-VCA-CO/RNN-VCA-CO. Published version

References in corpus (29)

• Adam: A Method for Stochastic Optimization
• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Ising formulations of many NP problems
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• A Critical Review of Recurrent Neural Networks for Sequence Learning
• Variational Inference with Normalizing Flows
• Parallel Tempering: Theory, Applications, and New Perspectives
• A class of quantum many-body states that can be efficiently simulated
• Theory of Quantum Annealing of an Ising Spin Glass
• GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
• Green Function Monte Carlo with Stochastic Reconfiguration
• Recurrent Neural Network Wave Functions
• Solving Statistical Mechanics Using Variational Autoregressive Networks
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Quantum annealing of the Traveling Salesman Problem
• Cyclical Annealing Schedule: A Simple Approach to Mitigating KL Vanishing
• Application of Quantum Annealing to Nurse Scheduling Problem
• Dilated Recurrent Neural Networks
• Variational Neural Annealing
• The Transformer Network for the Traveling Salesman Problem
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning
• Natural evolution strategies and variational Monte Carlo
• Training Binary Neural Networks using the Bayesian Learning Rule
• Supplementing Recurrent Neural Network Wave Functions with Symmetry and Annealing to Improve Accuracy
• Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization
• Many-Qudit representation for the Travelling Salesman Problem Optimisation
• The deep learning and statistical physics applications to the problems of combinatorial optimization
• Meta Variational Monte Carlo

Cited by in corpus (7)

• Investigating Topological Order using Recurrent Neural Networks
• Qudit-inspired optimization for graph coloring
• Recurrent neural network wave functions for Rydberg atom arrays on kagome lattice
• Sparse Autoregressive Neural Networks for Classical Spin Systems
• Liouville Space Neural Network Representation of Density Matrices
• Lattice Protein Folding with Variational Annealing
• Large-scale portfolio optimization with variational neural annealing