Combinatorial optimization problems widely exist in scientific research and engineering practice. From graph partitioning and logical reasoning to chip layout and task scheduling, almost all problems involving discrete decision-making can be attributed to some form of combinatorial optimization. However, since such problems are usually NP-hard, traditional algorithms face huge challenges in efficiency and scalability as the scale increases. How to achieve efficient and scalable solutions while maintaining problem versatility has always been a core problem in the field of combinatorial optimization.
In 2024, Zi-Song Shen and others proposed a new solution framework: Free-Energy Machine (FEM for short). This method relies on the principle of free energy minimization in statistical physics and combines automatic differentiation and gradient optimization technology in machine learning to build a unified, efficient, and parallel combinatorial optimization solver. In multiple benchmark tests, this method has demonstrated excellent accuracy and speed, as well as strong versatility and scalability.
Total text: 1911 words
Estimated reading time: 6 minutes
01 · Theoretical foundation and method construction
The core idea of FEM comes from statistical physics. The author abstracts the combinatorial optimization problem into an "energy function" E(σ), where σ represents all discrete variable configurations to be obtained. In physics, finding the lowest energy state of a system corresponds to finding its most stable structure at zero temperature, which corresponds to finding the optimal solution in an optimization problem.
Due to the difficulty of directly searching for the lowest energy configuration, FEM introduces a variational free energy function as a means of approximation. It weights energy and entropy by an adjustable parameter β, the reciprocal of temperature, resulting in the following free energy expression:
where PMF(σ) is an approximate probability distribution constructed through the variational method, in the form of a mean-field that is independent of each other. This distribution is parameterized using a softmax function, and the probability terms of all variables can be represented by differentiable functions, making the entire optimization process solvable with automatic differentiation tools.
During the optimization process, FEM simulates an "annealing" process that gradually cools from high temperature (high randomness) to low temperature (trends to the optimal solution), which is similar to the simulated annealing algorithm, but more systematically combines statistical physics theory and machine learning framework.
02 · Algorithm characteristics and technical advantages
FEM is designed to incorporate several advantages:
Strong versatility
Many traditional approximate optimization methods, such as Ising machines or QUBO solvers, are only suitable for specific forms of problems (e.g., binary variables, quadratic energy functions). FEM does not rely on a specific modeling structure. It can natively support multi-valued variables, high-order interaction terms and even constraint terms, and has extremely strong modeling capabilities.
High parallelism
All optimization operations are based on matrix multiplication, softmax function and vectorized calculations, which are very suitable for modern parallel hardware platforms such as GPU or FPGA, especially suitable for large-scale problem solving.
Optimizer mature
FEM uses optimizers widely used in deep learning (such as Adam), supports adaptive learning rate and first-order and second-order gradient estimation, and performs well in optimization efficiency and stability.
Copy mechanism enhances exploration capabilities
Inspired by replica symmetry breaking theory, FEM maintains multiple optimized replicas at the same time to jointly explore the solution space, thereby effectively avoiding falling into local optima.
FIG. 1. The framework of implementing Free-Energy Machine.
03 · Application verification and performance
The authors conducted in-depth testing of FEM in three typical categories of combinatorial optimization problems:
1·Max-Cut problem (Max-Cut)
FEM performs well on large-scale graphs such as K2000), and compared with the current strongest method dSBM in the G-set data set, it shows better time efficiency and solution quality.
FIG. 2. Benchmarking results for the maximum cut problem. Figure (a) shows FEM at K2000Solution quality distribution on the graph, Figure (c) shows the time efficiency comparison on different graph types.
2
Q-way balanced Min-Cut
This problem introduces multi-valued variables and global equilibrium constraints, posing challenges to modeling capabilities. FEM can not only flexibly model, but also surpass industrial-level partitioners such as METIS and KaFFPaE on multiple real graph data, especially in high-group number scenarios. In a large-scale chip verification problem containing nearly 1.5 million nodes, FEM's boundary communication overhead is reduced by 22%~26% compared to METIS.
3·Max k-SAT problem (Max k-SAT):
This type of problem involves high-order logical relationships. Among the 454 test instances of FEM in MaxSAT 2016, 448 reached the optimal solution, and the rest were only one logic short. The average solution time is 0.074 seconds, which is much faster than heuristic methods such as Max-CTDS on traditional CPUs.
FIG. 3. Benchmarking results on the MaxSAT 2016 competition problems. Figure (a) shows the optimality comparison of the solution, and Figure (b) shows the computational time advantage.
These experimental results fully demonstrate that FEM has strong versatility and leading solving capabilities in combinatorial optimization problems of different types, structures, and scales.
04 · Potential applications and future directions
The modeling versatility and execution efficiency of FEM make it suitable for a range of practical problems, including:
-
Graph partitioning and load balancing (such as chip layout, parallel computing resource allocation)
-
Community discovery in social networks and graph neural networks
-
Complex logical reasoning and constraint solving (SAT, planning problems, etc.)
-
Multi-task scheduling and path planning (such as UAV missions, manufacturing scheduling)
In addition, the structure of FEM can be further expanded. For example, the author points out that more sophisticated physical models (such as TAP free energy, Bethe free energy) can be introduced to enhance the model's expression ability; or it can be combined with a neural network structure to improve the representation ability of variational distributions. These directions provide rich space for the theoretical deepening and practical implementation of FEM.
However, it is worth mentioning that FEM is theoretically universal, but currently it handles unconstrained optimization by default, and its effectiveness in the engineering field remains to be discussed.
Summary
Free Energy Machine (FEM) provides a general solution framework for combinatorial optimization, which has both theoretical integrity and engineering feasibility. It organically combines the idea of free energy minimization in statistical physics with the gradient optimization technology in machine learning, breaking the bottlenecks of traditional optimization algorithms in structural limitations and scale expansion.
For operations optimization researchers and practitioners who deal with large-scale discrete decision-making problems, FEM is not only a new tool worthy of attention, but may also become a mainstream direction in combinatorial optimization in the future.
The project code is open source and readers can visit the following link to learn more:
https://github.com/Fanerst/FEM
References:
[1] Z.-S. Shen et al., “Free-Energy Machine for Combinatorial Optimization,” Dec. 12, 2024, arXiv: arXiv:2412.09285. doi: 10.48550/arXiv.2412.09285.
Machine-translated from the Chinese original 用「Free Energy Machine」统一组合优化求解：跨越统计物理与机器学习的方法 (published 2025-06-26). WeChat original ↗