A GPU-Accelerated Population-Based Boltzmann Machine for Solving Combinatorial Optimization Problems

Monte Carlo methods such as Simulated Annealing and Parallel Tempering have been applied to Boltzmann Machines for solving NP-hard combinatorial optimization problems. In practice, their implementations have been limited to small population (only a few CPU cores), not in massively parallel hardware. In this work, we show that Population Annealing algorithm can be applied to Boltzmann Machines and increases their performance in massively parallel hardware. We implement a large-scale GPU-accelerated Population-Based Boltzmann Machine (PBBM) with Population Annealing algorithm for solving all-to-all connected quadratic unconstrained binary optimization problems with up to 20000 binary variables. For 1024-variable problems, PBBM is able to perform parallel energy evaluation and local field calculations on a population size of up to 640 parallel replicas about 500x faster than running replicas serially. Benchmark results on Max-Cut problems show that our implementation outperforms state-of-the-art optimizers and on average is 43x faster and has 2.5x less error.M.A.S.2021-11-30 00:00:0