EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization

Kyo Kuroki, Thiem Van Chu, Masato Motomura, Kazushi Kawamura

IEEE Transactions on Evolutionary Computation · 2026 · 1-1

DOI: 10.1109/tevc.2026.3690973 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Evolutionary Computation, 2026. Verfasst von Kyo Kuroki und 3 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: Japan Science and Technology Agency, Japan Society for the Promotion of Science.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In recent years, formulating various combinatorial optimization problems as Quadratic Unconstrained Binary Optimization (QUBO) has gained significant attention as a promising approach for efficiently obtaining optimal or near-optimal solutions. While QUBO offers a general-purpose framework, existing solvers often struggle with performance variability across different problems. This paper (i) theoretically analyzes Mean Field Annealing (MFA) and its variants--which are representative QUBO solvers, and reveals that their underlying self-consistent equations do not necessarily represent the minimum condition of the Kullback-Leibler divergence between the mean-field approximated distribution and the exact distribution, and (ii) proposes a novel method, the Annealed Mean Field Descent (AMFD), which is designed to address this limitation by directly minimizing the divergence. Through extensive experiments on five benchmark combinatorial optimization problems (Maximum Cut Problem, Maximum Independent Set Problem, Traveling Salesman Problem, Quadratic Assignment Problem, and Graph Coloring Problem), we demonstrate that AMFD exhibits superior performance in many cases and reduced problem dependence compared to state-of-the-art QUBO solvers and Gurobi--a state-of-the-art versatile mathematical optimization solver not limited to QUBO.

Förderung

  • Japan Science and Technology Agency
  • Japan Society for the Promotion of Science

Zitieren

APA

Kuroki, K., Chu, T. V., Motomura, M., & Kawamura, K. (2026). Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization. IEEE Transactions on Evolutionary Computation, 1-1. https://doi.org/10.1109/tevc.2026.3690973

Vancouver

Kuroki K, Chu TV, Motomura M, Kawamura K. Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization. IEEE Transactions on Evolutionary Computation. 2026:1-1. doi:10.1109/tevc.2026.3690973

BibTeX
@article{Kuroki2026,
  author = {Kuroki, Kyo and Chu, Thiem Van and Motomura, Masato and Kawamura, Kazushi},
  title = {Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization},
  journal = {IEEE Transactions on Evolutionary Computation},
  year = {2026},
  pages = {1--1},
  doi = {10.1109/tevc.2026.3690973}
}
Kostenlos starten →