Free-Energy Machine for Combinatorial Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929627795030016 |
|---|---|
| author | Shen, Zi-Song Pan, Feng Wang, Yao Men, Yi-Ding Xu, Wen-Biao Yung, Man-Hong Zhang, Pan |
| author_facet | Shen, Zi-Song Pan, Feng Wang, Yao Men, Yi-Ding Xu, Wen-Biao Yung, Man-Hong Zhang, Pan |
| contents | Finding optimal solutions to combinatorial optimization problems is pivotal in both scientific and technological domains, within academic research and industrial applications. A considerable amount of effort has been invested in the development of accelerated methods that leverage sophisticated models and harness the power of advanced computational hardware. Despite the advancements, a critical challenge persists, the dual demand for both high efficiency and broad generality in solving problems. In this work, we propose a general method, Free-Energy Machine (FEM), based on the ideas of free-energy minimization in statistical physics, combined with automatic differentiation and gradient-based optimization in machine learning. The algorithm is flexible, solving various combinatorial optimization problems using a unified framework, and is efficient, naturally utilizing massive parallel computational devices such as graph processing units (GPUs) and field-programmable gate arrays (FPGAs). We benchmark our algorithm on various problems including the maximum cut problems, balanced minimum cut problems, and maximum $k$-satisfiability problems, scaled to millions of variables, across both synthetic, real-world, and competition problem instances. The findings indicate that our algorithm not only exhibits exceptional speed but also surpasses the performance of state-of-the-art algorithms tailored for individual problems. This highlights that the interdisciplinary fusion of statistical physics and machine learning opens the door to delivering cutting-edge methodologies that will have broad implications across various scientific and industrial landscapes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_09285 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Free-Energy Machine for Combinatorial Optimization Shen, Zi-Song Pan, Feng Wang, Yao Men, Yi-Ding Xu, Wen-Biao Yung, Man-Hong Zhang, Pan Statistical Mechanics Disordered Systems and Neural Networks Optimization and Control Computational Physics Finding optimal solutions to combinatorial optimization problems is pivotal in both scientific and technological domains, within academic research and industrial applications. A considerable amount of effort has been invested in the development of accelerated methods that leverage sophisticated models and harness the power of advanced computational hardware. Despite the advancements, a critical challenge persists, the dual demand for both high efficiency and broad generality in solving problems. In this work, we propose a general method, Free-Energy Machine (FEM), based on the ideas of free-energy minimization in statistical physics, combined with automatic differentiation and gradient-based optimization in machine learning. The algorithm is flexible, solving various combinatorial optimization problems using a unified framework, and is efficient, naturally utilizing massive parallel computational devices such as graph processing units (GPUs) and field-programmable gate arrays (FPGAs). We benchmark our algorithm on various problems including the maximum cut problems, balanced minimum cut problems, and maximum $k$-satisfiability problems, scaled to millions of variables, across both synthetic, real-world, and competition problem instances. The findings indicate that our algorithm not only exhibits exceptional speed but also surpasses the performance of state-of-the-art algorithms tailored for individual problems. This highlights that the interdisciplinary fusion of statistical physics and machine learning opens the door to delivering cutting-edge methodologies that will have broad implications across various scientific and industrial landscapes. |
| title | Free-Energy Machine for Combinatorial Optimization |
| topic | Statistical Mechanics Disordered Systems and Neural Networks Optimization and Control Computational Physics |
| url | https://arxiv.org/abs/2412.09285 |