Ising machines have attracted attention, which is expected to obtain better solutions of various combinatorial optimization problems at high speed by mapping the problems to natural phenomena. A slot-placement problem is one of the combinatorial optimization problems, regarded as a quadratic assignment problem, which relates to the optimal logic-block placement in a digital circuit as well as optimal delivery planning. Here, we propose a mapping to the Ising model for solving a slot-placement problem with additional constraints, called a constrained slot-placement problem, where several item pairs must be placed within a given distance. Since the behavior of Ising machines is stochastic and we map the problem to the Ising model which uses the penalty method, the obtained solution does not always satisfy the slot-placement constraint, which is different from the conventional methods such as the conventional simulated annealing. To resolve the problem, we propose an interpretation method in which a feasible solution is generated by post-processing procedures. We measured the execution time of an Ising machine and compared the execution time of the simulated annealing in which solutions with almost the same accuracy are obtained. As a result, we found that the Ising machine is faster than the simulated annealing that we implemented.

Ising machines have attracted attention as they are expected to solve combinatorial optimization problems at high speed with Ising models corresponding to those problems. An induced subgraph isomorphism problem is one of the decision problems, which determines whether a specific graph structure is included in a whole graph or not. The problem can be represented by equality constraints in the words of combinatorial optimization problem. By using the penalty functions corresponding to the equality constraints, we can utilize an Ising machine to the induced subgraph isomorphism problem. The induced subgraph isomorphism problem can be seen in many practical problems, for example, finding out a particular malicious circuit in a device or particular network structure of chemical bonds in a compound. However, due to the limitation of the number of spin variables in the current Ising machines, reducing the number of spin variables is a major concern. Here, we propose an efficient Ising model mapping method to solve the induced subgraph isomorphism problem by Ising machines. Our proposed method theoretically solves the induced subgraph isomorphism problem. Furthermore, the number of spin variables in the Ising model generated by our proposed method is theoretically smaller than that of the conventional method. Experimental results demonstrate that our proposed method can successfully solve the induced subgraph isomorphism problem by using the Ising-model based simulated annealing and a real Ising machine.

In an amusement park, an attraction-visiting route considering the waiting time and traveling time improves visitors' satisfaction and experience. We focus on Ising machines to solve the problem, which are recently expected to solve combinatorial optimization problems at high speed by mapping the problems to Ising models or quadratic unconstrained binary optimization (QUBO) models. We propose a mapping of the visiting-route recommendation problem in amusement parks to a QUBO model for solving it using Ising machines. By using an actual Ising machine, we could obtain feasible solutions one order of magnitude faster with almost the same accuracy as the simulated annealing method for the visiting-route recommendation problem.

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.