Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908313723076608 |
|---|---|
| author | Kuroki, Kyo Van Chu, Thiem Motomura, Masato Kawamura, Kazushi |
| author_facet | Kuroki, Kyo Van Chu, Thiem Motomura, Masato Kawamura, Kazushi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_08315 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization Kuroki, Kyo Van Chu, Thiem Motomura, Masato Kawamura, Kazushi Optimization and Control Neural and Evolutionary Computing 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. |
| title | Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization |
| topic | Optimization and Control Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2504.08315 |