Shortens computation time of problems with more than 100,000 variables by up to 20% with up to 35% greater precision
Hitachi and Rakuten Institute of Technology, Rakuten Group’s R&D organization (hereinafter, “Rakuten”) have developed a novel faster and more accurate method for solving large-scale combinatorial optimization problems. The newly developed method, combining Hitachi’s CMOS annealing technology*1 with Rakuten’s graph neural network (GNN) technology,*2 is able to reduce computation time by up to 20% and improve accuracy by up to 35% when solving large-scale problems with more than 100,000 variables, compared to the use of GNN technology alone. This advance is expected to benefit many fields, in applications such as optimization of delivery schedules.
In fields from logistics to finance, the ability to solve large-scale combinatorial optimization problems efficiently leads to improvement in service quality and cost reductions, and is therefore a key to making companies more competitive. By combining their respective technologies, Hitachi and Rakuten have developed a new problem solving method.
The developed method consists of two steps. Firstly, the method compresses the main GNN and generates multiple sub-GNN structures with different sizes, and applies CMOS annealing technology to compute the solutions. Secondly, using the obtained solutions as training data, it trains each sub-GNN and feeds the results back to the main GNN. This scheme contributes to shorter computation time and more accurate results (Figure 1).
To verify the effectiveness of the developed method, it was applied to maximum independent set problems*3 and maximum cut problems*4, which can be applied to social network analysis. The results confirmed that with a problem of more than 100,000 variables, computation time is reduced by up to 20% and calculation accuracy is improved by up to 35% compared to the use of GNN technology alone.*5
Hitachi plans to promote technology tie-ups with partners including universities and academia in general, seeking to apply this technology to fields such as materials development, recommendation systems, and electric power supply-related business.
The results of this development were announced in part at the ML with New Compute Paradigms (MLNCP) workshop at NeurIPS 2024, held in Vancouver, Canada on December 15, 2024.*6
Figure 1: Overview of the new approach to high-speed and high-accuracy solving of large-scale combinatorial optimization problems
*1 CMOS annealing technology: Technology that uses CMOS semiconductor devices to simulate the behavior of the Ising model. With this technology, computers operating at room temperature can efficiently find feasible solutions to combinatorial optimization problems.
*2 Graph neural network (GNN): A type of neural network capable of handling data in network (graph) structure. Whereas conventional neural networks are mainly intended for use with image and text data, a GNN is a machine learning model for learning graph-structured data. Its scalability allows it to handle problems containing as many as several million to hundreds of millions of nodes and edges.
*3 Maximum independent set problem: A problem of selecting the largest set of graph nodes in which none of the nodes are adjacent to each other.
*4 Maximum cut problem: A problem of partitioning a graph into two sets of nodes such that the number of edges between the two sets is as large as possible.
*5 Having the sub GNNs perform unsupervised learning without using the solutions from CMOS annealing and feeding back the results to the main GNN.
*6 “Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization”https://arxiv.org/abs/2501.05845
Related Information
Rakuten and Hitachi Collaborate at NeurIPS 2024 Workshop | News | Rakuten Institute of Technology
For more information, use the enquiry form below to contact the Research & Development Group, Hitachi, Ltd. Please make sure to include the title of the article.
https://www8.hitachi.co.jp/inquiry/hitachi-ltd/hqrd/news/en/form.jsp
