A Coherent Ising Machine Applied to Asymmetric Traveling Salesman Problems

Yukio Murata, Hiroyuki Yasuda, Kaori Kuroda +2 more

Mikio Hasegawa, Hirotake Ito, Hiroki Takesue +1 more

Recently, new optimization machines based on non-silicon physical systems, such as quantum annealing machines, have been developed, and their commercialization has been started. These machines solve the problems by searching the state of the Ising spins, which minimizes the Ising Hamiltonian. Such a property of minimization of the Ising Hamiltonian can be applied to various combinatorial optimization problems. In this paper, we introduce the coherent Ising machine (CIM), which can solve the problems in a milli-second order, and has higher performance than the quantum annealing machines especially on the problems with dense mutual connections in the corresponding Ising model. We explain how a target problem can be implemented on the CIM, based on the optimization scheme using the mutually connected neural networks. We apply the CIM to traveling salesman problems as an example benchmark, and show experimental results of the real machine of the CIM. We also apply the CIM to several combinatorial optimization problems in wireless communication systems, such as channel assignment problems. The CIM's ultra-fast optimization may enable a real-time optimization of various communication systems even in a dynamic communication environment.

Hiroki Takesue

Anton V. Eremeev, Yulia Kovalenko

This paper proposes quantum-accelerated optimal recombination operators (optimized crossovers) to be used in genetic algorithms for the traveling salesman problem (TSP) and makespan minimization on a single machine with setup times. For the symmetric TSP with adjacency-based encoding, the Optimal Recombination Problem (ORP) reduces to a TSP on a graph with maximum vertex degree 4 and a set of forced edges. Applying the quantum speedup result of Moylett, Linden, and Montanaro (2017), we obtain a bounded-error quantum crossover algorithm. In the case of asymmetric TSP (ATSP) with adjacency-based encoding, the ORP reduces to the ATSP on qubic graphs, so a modification of the quantum algorithm from Moylett, Linden, and Montanaro (2017) yields a bounded-error optimized crossover. Both quantum crossovers for the TSP and ATSP have time complexity bounds, smaller by exponential factors (in the number of vertices), compared to previously known optimized crossovers for these problems. For makespan minimization on a single machine with position-based encoding, the ORP reduces to a quadratic unconstrained binary optimization (QUBO) formulation, enabling solution by quantum annealers. The QUBO has at most ⌊k/2⌋ binary variables and, for almost all problem instances, only O(log k) binary variables, where k is the number of jobs.

Takahiro Inagaki

Qichao Tao, Jie Han

Annealing-based Ising machines have shown promising results in solving combinatorial optimization problems. As a typical class of these problems, however, traveling salesman problems (TSPs) are very challenging to solve due to the constraints imposed on the solution. This article proposes a parallel annealing algorithm for a fully connected Ising machine that significantly improves the accuracy and performance in solving constrained combinatorial optimization problems such as the TSP. Unlike previous parallel annealing algorithms, this improved parallel annealing (IPA) algorithm efficiently solves TSPs using an exponential temperature function with a dynamic offset. Compared with digital annealing (DA) and momentum annealing (MA), the IPA reduces the run time by 44.4 times and 19.9 times for a 14-city TSP, respectively. Large scale TSPs can be more efficiently solved by taking a k-medoids clustering approach that decreases the average travel distance of a 22-city TSP by 51.8% compared with DA and by 42.0% compared with MA. This approach groups neighboring cities into clusters to form a reduced TSP, which is then solved in a hierarchical manner by using the IPA algorithm.