2024-06-10 カリフォルニア大学サンディエゴ校(UCSD)
＜関連情報＞
- https://today.ucsd.edu/story/advanced-ai-based-techniques-scale-up-solving-complex-combinatorial-optimization-problems
- https://www.nature.com/articles/s42256-024-00833-7
ハイパーグラフ・ニューラルネットワークを活用した分散制約組み合わせ最適化 Distributed constrained combinatorial optimization leveraging hypergraph neural networks
Nasimeh Heydaribeni,Xinrui Zhan,Ruisi Zhang,Tina Eliassi-Rad & Farinaz Koushanfar
Nature Machine Intelligence Published:30 May 2024
DOI:https://doi.org/10.1038/s42256-024-00833-7
Abstract
Scalable addressing of high-dimensional constrained combinatorial optimization problems is a challenge that arises in several science and engineering disciplines. Recent work introduced novel applications of graph neural networks for solving quadratic-cost combinatorial optimization problems. However, effective utilization of models such as graph neural networks to address general problems with higher-order constraints is an unresolved challenge. This paper presents a framework, HypOp, that advances the state of the art for solving combinatorial optimization problems in several aspects: (1) it generalizes the prior results to higher-order constrained problems with arbitrary cost functions by leveraging hypergraph neural networks; (2) it enables scalability to larger problems by introducing a new distributed and parallel training architecture; (3) it demonstrates generalizability across different problem formulations by transferring knowledge within the same hypergraph; (4) it substantially boosts the solution accuracy compared with the prior art by suggesting a fine-tuning step using simulated annealing; and (5) it shows remarkable progress on numerous benchmark examples, including hypergraph MaxCut, satisfiability and resource allocation problems, with notable run-time improvements using a combination of fine-tuning and distributed training techniques. We showcase the application of HypOp in scientific discovery by solving a hypergraph MaxCut problem on a National Drug Code drug-substance hypergraph. Through extensive experimentation on various optimization problems, HypOp demonstrates superiority over existing unsupervised-learning-based solvers and generic optimization methods.
