Annealed Mean Field Descent beats Gurobi on 5 QUBO benchmarks
New solver minimizes KL divergence directly, improving accuracy and reducing variability across problems.
Quadratic Unconstrained Binary Optimization (QUBO) has become a popular framework for tackling combinatorial optimization problems, but existing solvers often suffer from inconsistent performance across different problem types. In a new paper accepted to IEEE Transactions on Evolutionary Computation, researchers from Tokyo Institute of Technology (Kyo Kuroki, Thiem Van Chu, Masato Motomura, Kazushi Kawamura) analyze Mean Field Annealing (MFA) and its variants, revealing a critical flaw: their self-consistent equations do not necessarily represent the minimum of the Kullback-Leibler divergence between the mean-field approximated distribution and the exact distribution.
To address this, the team introduces Annealed Mean Field Descent (AMFD), which directly minimizes this divergence. Through extensive experiments on five benchmark problems—Maximum Cut, Maximum Independent Set, Traveling Salesman Problem, Quadratic Assignment Problem, and Graph Coloring—AMFD demonstrates superior solution quality in many cases and notably reduced problem dependence compared to state-of-the-art QUBO solvers and Gurobi, a leading general-purpose mathematical optimizer. This suggests AMFD is a more robust general-purpose approach for combinatorial optimization, potentially enabling faster and more reliable solutions across industrial scheduling, logistics, and network design applications.
- AMFD directly minimizes KL divergence, unlike traditional MFA solvers
- Outperforms Gurobi and SOTA QUBO solvers on 5 benchmark problems
- Shows significantly reduced performance variability across problem types
Why It Matters
A more reliable QUBO solver means businesses can apply optimization to complex logistics and scheduling without per-problem tuning.