Combinatorial optimization problems often arise naturally in various fields of research. However, finding the global optimum solution of these problems remains computationally difficult. Ising spin model is considered to be an effective method to solve combinatorial optimization problems because these problems can be mapped and embedded into the Ising spin model. In general, Ising spin model requires to adjust and tune the spin connection parameters, for example, topology of spin connection and resolution of exchange interaction coefficient values between spins, according to the problems. In this paper, we focus on the number of spin connection, which is one of the spin connection parameters, and perform the calculation experiments through solving max-cut problems with Ising spin computing. As a result, all-to-all connectivity makes Ising spin computing well suited for searching the ground states of complex combinatorial optimization problems.
Combinatorial optimization problems often arise naturally in various fields of research. However, finding the global optimum solution of these problems remains computationally difficult. Ising spin model is considered to be an effective method to solve combinatorial optimization problems because these problems can be mapped and embedded into the Ising spin model. In general, Ising spin model requires to adjust and tune the spin connection parameters, for example, topology of spin connection and resolution of exchange interaction coefficient values between spins, according to the problems. In this paper, we focus on the number of spin connection, which is one of the spin connection parameters, and perform the calculation experiments through solving max-cut problems with Ising spin computing. As a result, all-to-all connectivity makes Ising spin computing well suited for searching the ground states of complex combinatorial optimization problems.
Recently, a new computing architecture using Ising spin model is gaining increasing attention. The Ising spin model is considered as an efficient computing method to solve combinatorial optimization problems. Depending on the problems, Ising spin model requires the tuning of spin connection parameters, such as an arbitrary topology and range of interaction coefficient values on the spin connection. In this work, we investigated computational properties of Ising spin model with the various spin connection parameters through solving combinatorial optimization problems. Consequently, the architecture with fully connectable spins makes Ising spin model well suited for solving complex combinatorial optimization problems.
Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical Ising model, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.
Ising machines are being developed as an efficient computing alternative for solving combinatorial optimization problems. Ising machines solve a combinatorial optimization problem by transforming it into a data structure called an Ising model. However, Ising machines have hardware limitations and hence the input Ising model coefficients must be limited to a certain range. Existing coefficient bit-width reducing methods do not guarantee that the output solution is optimum without adding too many extra spins. In this paper, we propose a new bit-width reducing method for Ising models. In this method, we first partition an original Ising model into several Ising models, each of which has the same graph topology, and the coefficient bit-width is reduced to be dealt with by the target Ising machine. Next, we obtain a ground-state solution for every partitioned Ising model. At that time, we can theoretically prove that, if all the partitioned Ising models have a common ground-state solution, it also gives a ground-state solution for the original non-bit-width-reduced Ising model. Experimental results demonstrate that the theorem is empirically true.
Annealing machines have been developed as non-von Neumann computers aimed at solving combinatorial optimization problems efficiently. To use annealing machines for solving combinatorial optimization problems, we have to represent the objective function and constraints by an Ising model, which is a theoretical model in statistical physics. Further, it is necessary to transform the Ising model according to the hardware limitations. In the transformation, the process of effectively reducing the bit-widths of coefficients in the Ising model has hardly been studied so far. Thus, when we consider the Ising model with a large bit-width, a naive method, which means right bit-shift, has to be applied. Since it is expected that obtaining highly accurate solutions is difficult by the naive method, it is necessary to construct a method for efficiently reducing the bit-width. This article proposes methods for reducing the bit-widths of interaction and external magnetic field coefficients in the Ising model and proves that the reduction gives theoretically the same ground state of the original Ising model. The experimental evaluations also demonstrate the effectiveness of our proposed methods.
This research is concerned with an annealing processor for efficiently solving a combinatorial optimization problem.\nIn order to realize a smart society, optimization of people and thingssuch as transportation networks, power networks, human resource allocationand routes is indispensable. Many of these problems are called combinatorial optimization problems and are known as very important problems in modern society. However, it is known that the combinatorial optimization problem is NP-hard and it is difficult to efficiently solve it with a conventional Neumann computer.\nIn recent years, the miniaturization of the process of manufacturing computer chips is approaching the physical limit. Therefore, especially in the solution by the full search, the improvement in speed due to the calculation speed of the computer cannot be expected. From such a background, dedicated hardware capable of solving a combination optimization problem at high speed and with low power consumption has been attracting attention.\nThe annealing processor is a general-purpose combination optimization solver that utilizes the property that the ground state of the optimization problem expressed by using the Ising model and the optimal solution of the combination optimization problem match. The Ising model is a ferromagnetic model in statistical physics expressed by spins having an upward and downward state, spin-spin interactions occurring between the spins, and an external magnetic field acting on each spin. The Ising model can express a combinatorial optimization problem by expressing a control target and a cost using these parameters. The annealing processor updates the spin state while slowly lowering the temperature parameters based on simulated annealing,which is an optimization method learned from natural phenomena generally called annealing. Eventually, the spin will reach the ground state with a high probability and obtain the optimal solution.\nAnnealing processors are classified into two types, the nearest neighbor type and the fully connected type, depending on the shape of the Ising model simulated on the hardware. In the nearest neighbor type, the coupling between spins is limited to only between adjacent spins, and in the full coupling type, coupling exists between arbitrary spins. The nearest neighbor type realizes high parallel processing by reducing the data spin required by simulated annealing by reducing the proximity spin. In addition, since data transfer is limited to adjacent spins, the scalability is high. However, since the spin-to-spin interaction is sparse, there is a problem that the class of combinatorial optimization problems that can be dealt with is limited, or that the problem requires deformation processing to match the Ising model of hardware. The fully connected type can solve any class of problems as long as the number of spins permits, however it requires connections between arbitrary spins.Therefore, scalability is low. Because there there is a dependency on all spins,the number of spins that can be updated at one time is always limited to only one regardless of the total number of spins. Therefore, it takes time to converge to the ground state.\nIn this research, we propose a method of increasing the number of spins for this annealing processor by using (1) a spatially-expanded time-division processing mechanism architecture based on a loosely-coupled type, (2) An algorithm for applying a fully coupled Ising network to a more complex Ising network using the nearest neighbor Ising network and an annealing method that can be updated in parallel, (3)We conducted a study on the architecture of a fully coupled annealing processor for parallel updating annealing.\nAs described above, the research described in this paper contributes to the improvement of the efficiency of the annealing processor for solving the large-scale combinatorial optimization problem from both the fundamental algorithm and the hardware architecture. I hope that this research will solve the combinatorial optimization problem that is expected to increase in demand in the future and contribute to the development of human society.
The Ising model provides a natural mapping for many computationally hard combinatorial optimization problems (COPs). Consequently, dynamical system-inspired computing models and hardware platforms that minimize the Ising Hamiltonian, have recently been proposed as a potential candidate for solving COPs, with the promise of significant performance benefit. However, the Ising model, and consequently, the corresponding dynamical system-based computational models primarily consider quadratic interactions among the nodes. Computational models considering higher order interactions among Ising spins remain largely unexplored. Therefore, in this work, we propose dynamical-system-based computational models to consider higher order (>2) interactions among the Ising spins, which subsequently, enables us to propose computational models to directly solve many COPs that entail such higher order interactions (COPs on hypergraphs). Specifically, we demonstrate our approach by developing dynamical systems to compute the solution for the Boolean NAE-K-SAT (K is greater than 3) problem as well as solve the Max-K-Cut of a hypergraph. Our work advances the potential of the physics-inspired 'toolbox' for solving COPs.