Free-energy machine for combinatorial optimization

Abstract

Finding optimal solutions to combinatorial optimization problems (COPs) is pivotal in both scientific and industrial domains. Considerable efforts have been invested on developing accelerated methods utilizing sophisticated models and advanced computational hardware. However, the challenge remains to achieve both high efficiency and broad generality in problem-solving. Here we propose a general method, free-energy machine (FEM), based on the ideas of free-energy minimization in statistical physics, combined with automatic differentiation and gradient-based optimization in machine learning. FEM flexibly addresses various COPs within a unified framework and efficiently leverages parallel computational devices such as graphics processing units. We benchmark FEM on diverse COPs including maximum cut, balanced minimum cut and maximum k-satisfiability, scaled to millions of variables, across synthetic and real-world instances. The findings indicate that FEM remarkably outperforms state-of-the-art algorithms tailored for individual COP in both efficiency and efficacy, demonstrating the potential of combining statistical physics and machine learning for broad applications.