Skip to main content

Hitachi

Corporate InformationResearch & Development

October 18, 2019

Table 1 A line-up of CMOS annealing that can address a variety of optimization problems

Hitachi, Ltd. has developed an optimization algorithm for fully connected models to find practical solutions quickly for large-scale optimization problems, such as scheduling optimization and portfolio optimization problems. The algorithm was implemented on GPUs and tested using fully connected combinatorial optimization problems with 100,000 variables*4. We confirmed that the approximate solution could be obtained 250 times faster than the conventional algorithm running on a modern CPU*5. Using this algorithm and CMOS annealing machine developed by Hitachi, a wide range of real problems faced by customers can now be addressed (Table 1). Going forward, Kyōsō-no-Mori*6 opened by Hitachi will be used as a research and development base to accelerate the creation of innovation through open collaboration. Through Kyōsō-no-Mori, Hitachi will work with internal and external partners to promote the production of solutions that contribute to solving increasingly complex social problems.

Background and challenges addressed

  • CMOS annealing and quantum annealing are attracting attention to solve quickly complex problems in the real world, such as traffic jams in cities.
  • Hitachi has developed CMOS annealing machines that can solve traffic congestion reduction problems with low power consumption. However, for certain problems such as portfolio optimization, some are difficult to solve because most of the variables are related.

Development technology

  • Development of optimization algorithms (Momentum Annealing: MA) that can obtain practical solutions in a short time for large-scale combinatorial optimization problems
    1. Parallel computing for combinatorial optimization problems with connections between arbitrary variables
    2. Calculation of the strength of an interaction using the eigenvalues of a matrix representing the connections
    3. Faster solution search by parallel computing utilizing GPUs

Confirmed effect

  • The effectiveness of the MA was verified by solution search using a fully connected Ising model with 100,000 spins. We confirmed that the MA can perform 250 times faster than the conventional algorithm (Simulated Annealing: SA).

Papers, academic conferences, events, etc.

Details of the developed technology

1. Parallel computing for combinatorial optimization problems with connections between arbitrary variables

The algorithm proposed by Hitachi is called Momentum Annealing (MA), which solves a combinatorial optimization problem called QUBO*7. MA converts a QUBO (Figure 1a), in which all variables are connected to one another, into another QUBO (Figure 1b) where the variables connect in the form of a complete bipartite graph, while maintaining an optimum solution. The optimization algorithm based on the Markov chain Monte Carlo method represented by Simulated Annealing (SA) guarantees to reach the optimal solution or its approximate solution by updating variables sequentially and stochastically. Although variables that are not connected to any others can be independently and simultaneously updated, simultaneous updates cannot be made under any other conditions. Therefore, when we solve a fully connected QUBO, we can update only one variable at a time. However, if the connection between variables is in the form of a complete bipartite graph, the variables on the left in Figure 1b are not connected and can be updated at the same time. The same is true for the variables on the right. Therefore, we can execute parallel computation and reduce the time.


Fig. 1 Conversion of Ising model into bipartite graph.

2. Calculation of the strength of an interaction using the eigenvalues of a matrix representing the connections

MA searches the solution using the model with the new connection shown by the red line in Figure 1b. If the effect of these connections is too significant, it is more likely to be trapped in the local solution, making it difficult to find a good solution by exploring various states. On the other hand, if the coupling is too small, the optimal solution of QUBO (Figure 1a) to be solved and that of QUBO (Figure 1b) dealt with in MA will be different and not appropriate. It is necessary to make the new connection as small as possible while the optimum solution of each problem agrees. To achieve this goal, we derived an inequality using the maximum eigenvalue of the matrix representing the connection between the variables and set the strength of the connection of the red line appropriately.

3. Faster solution search by parallel computing utilizing GPUs

To conduct quick solution searching for QUBO with all variables connecting to one another, we generated an MA program that makes use of GPUs that are widely used for scientific computing such as deep learning. To solve QUBOs with 100,000 variables, we ran MA on 4 NVIDIA Tesla P100*8 and reported that it took 1/250 of the computational time to reach an accurate solution equivalent to an approximate solution obtained with the Sahni-Gonzales (SG) optimization algorithm compared with the SA run on IBM Power 8*9 (Figure 2).


Fig. 2 Experimental results obtained with MA and SA solving a fully connected Ising model with 100,000 spins. The horizontal axis represents the computation time and the vertical axis represents the objective function value of the combinatorial optimization problem.

*1
GPU: Abbreviation for Graphic Processing Unit. A processor used in deep learning and a variety of scientific and technical calculations.
*2
ASIC: Abbreviation for Application Specific Integrated Circuit
*3
FPGA: Abbreviation for Field Programmable Gate Array. An integrated circuit whose configuration can be set by a designer after manufacture.
*4
The combinatorial optimization problem referred to here is finding the ground state of Ising models.
*5
The conventional algorithm is Simulated Annealing.
*6
News Releases from Hitachi "A New Research Initiative to Accelerate Innovation through Open Collaborative Creation with Partners" http://www.redflecks.com/New/cnews/month/2019/04/190411.html
*7
QUBO: Abbreviation for Quadratic Unconstrained Binary Optimization. It is a kind of combinatorial optimization problem.
*8
NVIDIA and Tesla are registered trademarks of NVIDIA Corporation in the United States and/or other countries.
*9
IBM and POWER8 are trademarks of International Business Machines Corporation, registered in many countries around the world.

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.

日本黄色