Free-energy machine for combinatorial optimization.

Area of Science:

• Computational Physics
• Machine Learning
• Operations Research

Background:

• Combinatorial optimization problems (COPs) are crucial in science and industry.
• Existing methods often lack both efficiency and generality.
• Advanced computational hardware and models have improved but not fully solved this challenge.

Purpose of the Study:

• To introduce a general and efficient method for solving diverse combinatorial optimization problems.
• To leverage principles from statistical physics and machine learning for a unified approach.
• To demonstrate the method's performance on large-scale, real-world problems.

Main Methods:

• Developed a Free-Energy Machine (FEM) based on free-energy minimization.
• Integrated automatic differentiation and gradient-based optimization from machine learning.
• Utilized parallel computation on graphics processing units for efficiency.

Main Results:

• FEM was benchmarked on maximum cut, balanced minimum cut, and maximum k-satisfiability problems.
• Performance was evaluated on instances scaled to millions of variables.
• FEM demonstrated superior efficiency and efficacy compared to state-of-the-art specialized algorithms.

Conclusions:

• The Free-Energy Machine (FEM) offers a unified framework for addressing various COPs.
• Combining statistical physics and machine learning provides a powerful approach for optimization.
• FEM shows significant potential for broad scientific and industrial applications.