  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.
