Fujitsu Laboratories Limited has successfully developed a new parallel search technology to help achieve megabit-class performance for large-scale problems, representing an important technical milestone for its Digital Annealer. Fujitsu’s Digital Annealer is a unique computing architecture that rapidly solves combinatorial optimisation problems too large and complex for conventional technologies.
The current, second-generation Digital Annealer Cloud Service, available to customers since May 2018, delivers performance at 8,192 bits to offer users a powerful tool for solving optimisation problems in fields including logistics, finance, medicine, and manufacturing. However, as applications in a variety of industries continue to grow, a need continues to exist for a technology that can handle problems at an even larger scale to solve a broader range of complex, real-world problems.
With this challenge in mind, Fujitsu Laboratories has successfully demonstrated the world’s first practical solution on the scale of one megabit for an Ising machine with its Digital Annealer, applying a new parallel search technology.
By integrating this technology into its Digital Annealer, Fujitsu Laboratories aims to contribute to solving real-world problems, furthering expanding its ability to solve large-scale combinatorial optimisation problems in a variety of fields.
Development Background and Challenges
With the acceleration of DX initiatives in the corporate world, users in many industries and disciplines increasingly face situations in which they need to quickly find the optimal solution among various combinations of factors in the real world, including in manufacturing, logistics, disaster prevention, and new drug development.
It has become necessary to solve combinatorial optimisation problems on the scale of one megabit to resolve these practical challenges. This remains difficult owing to the fact that obtaining an effective solution in a limited time causes an exponential increase in computational complexity.
For instance, in the manufacturing field, large-scale optimisation is needed to streamline production, including for scheduling complex manufacturing processes that differ from part to part across an entire plant, taking into account resources such as personnel and equipment, and delivery dates. It is necessary to not only optimise distribution plans on a regional scale but also to draw up large-scale plans covering the entire country in the logistics field.
Newly Developed Technology
Fujitsu Laboratories has extended its Digital Annealer architecture to develop a new parallel search technology that achieves high performance in solving large-scale problems. Fujitsu Laboratories has demonstrated the solution of a one megabit scale problem with the Digital Annealer leveraging this technology. The features of the newly developed technology are as follows.
1. Adaptive parallel search technology for large-scale problems
Digital Annealer achieves high search performance by constructing a basic optimisation module with a high degree of parallelism that repeatedly performs an update bit search to transition from a certain state to a more optimal state. Fujitsu Laboratories has developed an adaptive parallel search technology that performs the multi-bit update in the early stage when a rapid energy drop is expected due to multi-bit update, and switches to single-bit update to increase the solution search accuracy in the converging stage to solve large-scale problems.
2. Cooperative Search Technology in Multiple Server Parallel
To solve large-scale problems that cannot be handled by a single server, Fujitsu Laboratories has developed a technology to solve large-scale problems with multiple linked servers while ensuring consistency in overall solutions. By dividing a large problem into multiple subproblems and assigning them to multiple servers, the solution of the subproblem is shared among the servers, and the local search at each server is appropriately controlled while grasping the state of the overall solution. A large-scale solution system using this technology has made it possible to solve one megabit class large-scale problems.
Outcomes
Fujitsu Laboratories applied the new technology to solve the problem of determining the production schedule for a small batch of a wide variety of servers. It is necessary to consider complex constraints, including work order, worker skill level, break times, and equipment availability to solve this problem. The number of bits in the problem is determined by the number of discrete tasks, the number of workers, the number of pieces of equipment, and the number of time slots, and is very large. In this example, the test was conducted under the conditions of 100 tasks, 12 pieces of equipment, 13 workers, and 65-time slots, and the total number of bits was 1,014,000 bits. Fujitsu Laboratories successfully confirmed the solution of a practical problem at the one megabit level by applying the new technique to produce the solution.
Future Plans
Fujitsu Laboratories will apply the newly developed technology for the Digital Annealer to help solve various large-scale combinatorial optimisation problems in the real world, contributing to the streamlining of the development of new drugs, nationwide transportation and delivery plans, strategies for resolving traffic congestion in urban areas and work shift planning suitable for the new normal era.
Archive
- March 2024(112)
- February 2024(109)
- January 2024(95)
- December 2023(56)
- November 2023(86)
- October 2023(97)
- September 2023(89)
- August 2023(101)
- July 2023(104)
- June 2023(113)
- May 2023(103)
- April 2023(93)
- March 2023(129)
- February 2023(77)
- January 2023(91)
- December 2022(90)
- November 2022(125)
- October 2022(117)
- September 2022(137)
- August 2022(119)
- July 2022(99)
- June 2022(128)
- May 2022(112)
- April 2022(108)
- March 2022(121)
- February 2022(93)
- January 2022(110)
- December 2021(92)
- November 2021(107)
- October 2021(101)
- September 2021(81)
- August 2021(74)
- July 2021(78)
- June 2021(92)
- May 2021(67)
- April 2021(79)
- March 2021(79)
- February 2021(58)
- January 2021(55)
- December 2020(56)
- November 2020(59)
- October 2020(78)
- September 2020(72)
- August 2020(64)
- July 2020(71)
- June 2020(74)
- May 2020(50)
- April 2020(71)
- March 2020(71)
- February 2020(58)
- January 2020(62)
- December 2019(57)
- November 2019(64)
- October 2019(25)
- September 2019(24)
- August 2019(14)
- July 2019(23)
- June 2019(54)
- May 2019(82)
- April 2019(76)
- March 2019(71)
- February 2019(67)
- January 2019(75)
- December 2018(44)
- November 2018(47)
- October 2018(74)
- September 2018(54)
- August 2018(61)
- July 2018(72)
- June 2018(62)
- May 2018(62)
- April 2018(73)
- March 2018(76)
- February 2018(8)
- January 2018(7)
- December 2017(6)
- November 2017(8)
- October 2017(3)
- September 2017(4)
- August 2017(4)
- July 2017(2)
- June 2017(5)
- May 2017(6)
- April 2017(11)
- March 2017(8)
- February 2017(16)
- January 2017(10)
- December 2016(12)
- November 2016(20)
- October 2016(7)
- September 2016(102)
- August 2016(168)
- July 2016(141)
- June 2016(149)
- May 2016(117)
- April 2016(59)
- March 2016(85)
- February 2016(153)
- December 2015(150)