Pictures © Fujitsu
Despite the computing power provided by modern IT systems, the travelling salesman problem, a well-known problem from combinatorial optimisation, still poses a massive obstacle for many companies trying to optimise their processes. It asks the question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the city of origin?”. This optimisation problem can be seen, in a slightly modified version, in day-to-day business, for example, when you look at the dispatching of trucks and the order that they drive to the individual destinations in, when delivering or picking up goods. While the dispatching of a handful of vehicles and destinations can be easily handled manually, a large number on the other hand requires a tremendous amount of processing power for a computer to visit and evaluate all possible combinations. Usually, this processing power cannot be provided by basic IT resources in a practical and timely manner.
This is where quantum computers will come into play in future, by evaluating all possible options, in this case all possible orders, simultaneously. Until this technology becomes available, such optimisation problems can already be solved much faster by leveraging quantum-inspired technologies such as Digital Annealing. Fujitsu is now realising a technology solution that addresses this exact problem with the Digital Annealing Unit processor.
Digital Annealing: Fields of application.
There are several fields where Digital Annealing could provide significantly faster solutions for combinatorial optimisation tasks in the near future—compared to traditional approaches that are based on CPU and GPU technologies. Some examples are logistics planning and production, discrete optimisation in product design, or portfolio and risk management in finance.
1. Logistics planning.
Logisticians are often faced with the challenge of optimising the travel routes for the transport of goods. The total amount of combinations is not only made up of the amount of start and end points and the transport vehicles available, but also of the transport volume per vehicle and the evaluations of the travel routes. The challenge is to find the best option for assignment, routes and loading—and not just once, but on a regular basis and as fast as possible.
The potential Digital Annealing could offer here can be seen in this example from Japan: The Japanese postal service was able to reduce their transport vehicles in one distribution area from 52 down to 48. Costs sank by 7 percent, while the effectively-used transport volume rose by 12 percent and distribution was handled 30 percent faster. In another example, a US automotive supplier was able to save 5 percent of its transport costs by optimising its intralogistics.
2. Planning and optimising production.
Production planners often face similar challenges to those faced in logistics, when deciding on the best order for production tasks that are worked on manually as well as on machines (job shop scheduling). Even relatively straightforward tasks force the planner to make a decision between more than 10100 potential alternatives. In day-to-day business, companies often solve these tasks by implementing rule-based planning systems with limited quality, forcing the planning manager to readjust during production based on experience. The results often deviate heavily from what is desired. The upcoming trend of producing smaller lot sizes to suit customers’ individual needs has made it more difficult to plan this way.
Due to its real optimisation algorithm, Digital Annealing can offer a significantly improved selection from the more than 10100 alternatives possible. This happens so fast that the time it takes for calculation is almost completely negligible. For example, the time it takes to machine a series of 40 orders with 6 lathe and milling machines could be reduced by about 30 percent from 284 hours to 200 hours. The time it took to calculate this optimisation was less than a minute.
3. Discrete optimisation in product design.
Optimisation in the design of technical products often forces the designer to take several variables into account, for example, when designing a cable harness in a car, where hundreds of contact points inside the vehicle have to be connected in such a way that requires the shortest possible cable distance. The designer has to work while sticking to certain parameters, e.g. wiring the vehicle in such a way that the signalling and supply cable are not right next to each other. Even if the cable harness is not calculated to suit each vehicle specifically, the ability to leverage effective on-the-fly optimisations is essential, as the design process often requires a series of iterations of the same calculation in order to account for changing parameters.
4. Portfolio and risk management in finance.
Risk and portfolio managers in financial institutions often face the challenge of bundling individual items to make “packages”, which are categorised into distinct risk profiles. The challenge here is to make best use of the framework provided in order to create a diversified portfolio that is easier to implement and spreads the risk as much as possible.
Take Fujitsu for example, that has just finished a successful proof-of-concept project in the credit portfolio management sector in collaboration with Commerzbank’s research and development unit, Main Incubator. In a nutshell, the project was aimed at improving the choice and bundling of requirements in leasing contracts for cars. The goal was to optimise the choice process of some thousand individual requests by bundling them into one securitisation portfolio. In this choice process, several critical factors must be considered all at once, including guidelines, volume restrictions and percentual limitations for certain requirement aspects to make sure that the investors aren’t putting all of their eggs into one basket. The same goes here: Digital Annealing allows Main Incubator to make faster and more exact calculations.
Besides Main Incubator, British commercial bank NatWest also uses Digital Annealing. It helps the bank to optimise some of their most complex and demanding financial investment decisions.
The technology behind it all.
Simulated Annealing can help find the perfect solution to combinatorial optimisation problems that are formulated as so-called QUBOs (Quadratic Unconstrained Binary Optimisation). The Fujitsu Digital Annealing Unit (DAU) is a silicone-based CMOS chip stored directly inside the hardware that uses the Simulated Annealing algorithm with a focus on massively parallel processing and numerical optimisation. This allows these problem classes to be calculated up to 10,000 times faster than with full-fledged simulations ran on traditional architectures, provided that these are even technically possible.
For most companies a suitable model would be to book Digital Annealing as a service. For this, the Digital Annealing Cloud Service is tied to the company’s IT using application programming interfaces (APIs). Because quantum-inspired computers require very specific knowledge to provide tasks for the system appropriately, this service will be supported by some complimentary services.
Senior VIPM Fujitsu
Bechtle Logistics Neckarsulm
- Article: Quantum Dualism
- Fujitsu: More on Digital Annealing
- Webinar: Digital Annealing at the Bitkom Digitaltag Convention
Get the best from the Bechtle update every two months directly into your mailbox. Click here to register: