Applicable to large-scale optimization problems having hundreds of thousands of variables and tens of thousands of formulas expressing constraints
Hitachi has developed CMOS annealing technology for solving large-scale combinatorial optimization problems at high speed while satisfying complex constraints. This technology integrates CMOS annealing, with its high capability for optimization calculation of large-scale optimization problems having hundreds of thousands of variables and tens of thousands of formulas expressing constraints, and an optimization solver*1 with excellent performance in searching for solutions that meet the designated constraints, to derive solutions within realistic time frames. It further makes use of Alternating Direction Method of Multipliers (ADMM),*2 an algorithm that divides a problem into multiple smaller parts and efficiently solves each of them, to achieve high-precision optimization while distributing the computational load. It is therefore expected to contribute toward greater efficiency and sophistication of complex operational planning demanded in social infrastructure and the finance field, for example, such as in optimization of railway vehicle operation plans or financial portfolios. Hitachi plans to incorporate this technology in its CMOS Annealing Cloud Service,*3 and to further advance the technology in collaborative creation with customers, helping to solve various societal issues and realize a sustainable society.
In the social infrastructure and finance fields, large-scale operation management systems need to be operated efficiently while satisfying complex constraints. In the case of a railway vehicle operation plan, for example, each time the train schedule is revised, it is necessary to decide which trains using which railway vehicles are to be run.*4 Since many constraints have to be satisfied, such as the capacity of the train depot and the timing of regular inspections, devising an efficient train schedule that uses the minimum necessary railway vehicles takes considerable knowhow and time. For solving such large-scale combinatorial optimization problems, as technology for optimizing huge combinations of variables, Hitachi had previously developed the CMOS annealing technology “relaxed MA”*5 that uses not only binary variables with values of 0 and 1 but continuous variables,*6 for realizing more flexible optimization. There was still a need, however, to develop new technology to find solutions, within a realistic time frame, that satisfy even more complex and diverse constraints.
Hitachi has therefore developed new CMOS annealing technology for solving large-scale combinatorial optimization problems at high speed with satisfying complex constraints. In the new technology, CMOS annealing has the role of finding better solutions to large-scale optimization problems, while an optimization solver repeatedly searches in the vicinity of those solutions for solutions that satisfy the constraints, thereby deriving feasible solutions at high speed (Figure 1). In integrating CMOS annealing and the optimization solver, an algorithm called Alternating Direction Method of Multipliers (ADMM) is used, which by dividing up a combinatorial optimization problem is capable of efficiently finding solutions that meet the constraints for each readily solvable part. The technology is therefore able to solve at high speed large-scale optimization problems having hundreds of thousands of variables and tens of thousands of formulas expressing constraints.
Figure 1. CMOS annealing technology for fast solving of large-scale combinatorial optimization problems while satisfying the given constraints
Hitachi plans to incorporate this technology in its CMOS Annealing Cloud Service and, along with aiming for application to fields such as finance and railway services, to further advance the technology while verifying its value in collaborative creation with customers.
Some of the results of this development were announced in part at the International Workshop on Ising Machines (IISM) 2025, held in May 2025 in Evanston (near Chicago), Illinois, USA.
*1 Optimization solver: Software with algorithms for solving mathematical optimization problems. It has functions for searching for combinations of values that satisfy various constraints that are specified.
*2 Alternating Direction Method of Multipliers (ADMM): An algorithm for solving large-scale optimization problems by alternately and repeatedly solving subproblems (parts of the original problem) using multiple solving methods, in order to find a feasible solution to the whole problem. It has been the subject of many research reports, such as for use in distributed management systems in the energy field.
*3 News release of October 3, 2022, Hitachi Launches Cloud Service for Quantum Inspired Computer "CMOS Annealing"
*4 Here a “railway vehicle” is the physical vehicle body that actually runs, while a “train” is a virtual operational unit set in the train schedule. In actual operation, it is necessary to assign a railway vehicle, without omission, to all trains set in the schedule.
*5 News release of June 6, 2024, Hitachi develops CMOS annealing technology "relaxed MA" for supporting optimization tasks with continuous variables
*6 Continuous variable: A variable that differs from a binary variable, which can have the values 0 or 1 only, in being able to have values expressed by 32-bit or 64-bit floating decimal points between 0 and 1.
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.
https://www8.hitachi.co.jp/inquiry/hitachi-ltd/hqrd/news/en/form.jsp
