Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization
Preprint
Abstract
Combinatorial optimization problems are central to both practical applications and the development of optimization methods. While classical and quantum algorithms have been refined over decades, machine learning-assisted approaches are comparatively recent and have not yet consistently outperformed simple, state-of-the-art classical methods. Here, we focus on a class of Quadratic Unconstrained Binary Optimization (QUBO) problems, specifically the challenge of finding minimum energy configurations in three-dimensional Ising spin glasses. We use a Global Annealing Monte Carlo algorithm that integrates standard local moves with global moves proposed via machine learning. We show that local moves play a crucial role in achieving optimal performance. Benchmarking against Simulated Annealing and Population Annealing, we demonstrate that Global Annealing not only surpasses the performance of Simulated Annealing but also exhibits greater robustness than Population Annealing, maintaining effectiveness across problem hardness and system size without hyperparameter tuning. These results provide, to our knowledge, the first clear and robust evidence that a machine learning-assisted optimization method can exceed the capabilities of classical state-of-the-art techniques in a combinatorial optimization setting.Keywords
All Related Versions
This publication has 47 references indexed in Scilit:
- Hierarchical autoregressive neural networks in three-dimensional statistical systemComputer Physics Communications, 2025
- Unsupervised learning with GNNs for QUBO-based combinatorial optimizationEURO Journal on Computational Optimization, 2025
- Sampling metastable systems using collective variables and Jarzynski–Crooks pathsJournal of Computational Physics, 2025
- Searching for spin glass ground states through deep reinforcement learningNature Communications, 2023
- Skipping the Replica Exchange Ladder with Normalizing FlowsThe Journal of Physical Chemistry Letters, 2022
- Machine learning for combinatorial optimization: A methodological tour d’horizonEuropean Journal of Operational Research, 2021
- GPU accelerated population annealing algorithmComputer Physics Communications, 2017
- Breakout Local Search for the Max-CutproblemEngineering Applications of Artificial Intelligence, 2013
- The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspectivePhysics Reports, 2013
- Multi-spin coding: A very efficient technique for Monte Carlo simulations of spin systemsJournal of Computational Physics, 1981