A New Solution Method for Combinatorial Optimization Problems to Maximize the Computational Performance of GPU

Tokyo, 17 Aug. 2020 - NTT DATA Corporation and the research team of Hiroshima University, Graduate School of Advanced Science and Engineering led by Professor Koji Nakano have developed a new computational method, Adaptive Bulk Search, for high-speed search to retrieve solutions to the combinatorial optimization problems. This method uses multiple GPUs (Graphics Processing Units² to solve a quadratic unconstrained binary optimization (QUBO) problem¹efficiently in parallel. We use this method effectively to solve various problems including hard problems for conventional technologies, and to expand the application fields of quantum computers and next-generation architectures.

Background

Quantum annealers, GPUs, and FPGAs³ have been used to develop an architecture that solves the combinatorial optimization problems at high speed in the recent research and development activities. The combination optimization problems are applicable to a wide range of practical problems, which means that the computation capability to find the solution to these problems will lead to solve many social problems. The research and development of the new architecture, where various combinatorial optimization problems are integrated to a unified problem called QUBO problem, aim to solve the QUBO problem at high speed.

The features of our new method are "its flexibility for various QUBO problems" and "the large-scale computing system that can achieve acceleration proportional to the number of computers." These features realize flexible and scalable computation, and is expected to greatly expand the potential of this technology area beyond solving specific problems at a certain speed.

In January 2019, NTT DATA launched Quantum Computer and Next-Generation Architecture Lab Service⁴ to promote quantum computers and other next-generation architectural applications in various fields through the validations of these. Based on these validations, NTT Data provided applicable cases, evaluation methods and current problems, with which the Hiroshima University research team found the new solution method. NTT DATA will accelerate research and development activities to efficiently solve the unsolvable problems that are difficult to solve, even social issues in the future, through innovations in computing.

Overview

The new solution method, Adaptive Bulk Search, uses multiple algorithms to search in parallel for the best solution with the lowest cost from a large number of solutions on the GPU.

The Adaptive Bulk Search:

• can solve various QUBO problems by changing the search method flexibly;
• can increase the computation speed by using a larger computer system and supercomputer in proportion to the number of computing nodes; and
• was designed considering the features of the GPU architecture, and achieved a computation performance of over 1 trillion solutions per second using a server equipped with four latest NVIDIA GPUs⁵.

The experiment results show that the Adaptive Bulk Search can solve the problems including the maximum cut problem, the traveling salesman problem, and the random problem very efficiently. In addition, it can handle up to 32,768-bit QUBO problems at this time.

Details of the research will be presented by Associate Professor Ryota Yasudo of Hiroshima University at the International Conference on Parallel Processing (ICPP), which will be held from August 17 to 20. The ICPP is a traditional international conference on parallel processing, and this will be the 49^th edition.

(FIGURE: Yasudo, et.al., ICCP 2020)

Future Goals

NTT DATA will use this solution method to address various problems in the logistics, finance, and manufacturing industries, as well as to improve the performance of AI and machine learning. NTT DATA will also work with Hiroshima University to further improve the method to efficiently find solutions to unsolved difficult problems by expanding its applicability, in attempting to solve the social problems such as the issues of efficient energy use and smart logistics networks.

Conference Information