A new technique to solve complex optimization problems

Toshiba Corporation developed a new technique, called Simulated Bifurcation Algorithm, that quickly obtains highly accurate approximate solutions for complex large-scale combinatorial optimization problems. It can be applied to many essential tasks, such as identifying efficient delivery routes, determining the most effective molecular structures to investigate in new drug development, and building portfolios of profitable financial products

Many problems can only be solved by sifting through a vast number of options to find the best combinations. These include realizing efficient logistics (the traveling salesman problem in math), directing traffic to ease congestion, applying molecular design to drug development, and optimizing financial portfolios. Today, realizing such combinatorial optimization requires an enormous amount of computation, and using current computers to find solutions remains difficult.

There are growing expectations that next-generation computing devices, such as quantum computers, will lead the way to better solutions, and current research aims to develop computers specially designed for combinatorial optimization through the use of superconducting circuits, lasers, and semiconductor-based digital computers. Despite these efforts, it remains a challenge to increase the solvable-problem size and to reduce the computation time.

Toshiba has solved these issues by developing a novel combinatorial optimization algorithm, the Simulated Bifurcation Algorithm. It is highly parallelizable, and can therefore easily speed up problem solving on standard digital computer through parallel computation.

For example, by using field-programmable gate arrays (FPGAs), a good solution to an optimization problem with 2,000 fully connected variables (approximately 2 million connections) can be obtained in just 0.5 milliseconds. This is approximately 10 times faster than the laser-based quantum computer recognized as the world’s fastest can solve the same problem. In addition, using a cluster of eight GPUs, Toshiba obtained a good solution for a large-scale problem involving 100,000 fully connected variables (about 5 billion connections) in only a few seconds. These results open up new ways of solving large-scale combinatorial optimization problems in many different areas of application.

The Simulated Bifurcation Algorithm harnesses bifurcation phenomena, adiabatic processes, and ergodic processes in classical mechanics, to rapidly find highly accurate solutions. Toshiba derived the principle from a theory of a quantum computer proposed by the company itself.

Moving forward this year, Toshiba now aims to use this key technology breakthrough to realize and commercialize a service platform that meets all optimization needs in logistics, finance, and other areas.

 

Source: Toshiba Corporation