Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Consumer Electronics

A Multiple Coefficients Trial Method to Solve Combinatorial Optimization Problems for Simulated-annealing-based Ising Machines

Takehara Kota, Daisuke Oku, Yoshiki Matsuda, Shu Tanaka, Nozomu Togawa

Published Sep 8, 2019• 9 citations
Publisher

Abstract

When solving a combinatorial optimization problem with Ising machines, we have to formulate it onto an energy function of Ising model. Here, how to determine the penalty coefficients in the energy function is a great concern if it includes constraint terms. In this paper, we focus on a traveling salesman problem (TSP, in short), one of the combinatorial optimization problems with equality constraints. Firstly, we investigate the relationship between the penalty coefficient and the accuracy of solutions in a TSP. Based on it, we propose a method to obtain a TSP quasi-optimum solution, which is called multiple coefficients trial method. In our proposed method, we use an Ising machine to solve a TSP by changing a penalty coefficient every trial, the TSP solutions can converge very fast in total. Compared to naive methods using simulated-annealing-based Ising machines, we confirmed that our proposed method can reduce the total number of annealing iterations to 1/10 to 1/1000 to obtain a quasi-optimum solution in 32-city TSPs.

DOI
10.1109/icce-berlin47944.2019.8966167

Related papers

A Constraint Partition Method for Combinatorial Optimization Problems

Makoto Onoda, Kazuhiko Komatsu, Masahito Kumagai +2 more

Ising machines have attracted much attention in recent years because of their potential in solving combinatorial optimization problems that are difficult to be solved using conventional computers. Ising machines solve the optimization problem that can be transformed into a quadratic unconstrained binary optimization (QUBO) problem. In the case of a problem with constraints, named a constraint problem, an objective function and constraint function with penalty coefficients are combined into a single Hamiltonian of a QUBO problem. When solving a constraint problem, the accuracy of the solution decreases compared to a QUBO problem with an objective function only. This is because penalty coefficients are set to excessively large values to prevent constraint violations. As a result, it becomes difficult to minimize the objective function. To solve this problem, this paper proposes a method that partitions constraint functions and reduces the value of the penalty coefficients. The performance evaluation using the traveling salesperson problem (TSP) with one-hot constraints demonstrates that the proposed method can improve the solution accuracy compared to the conventional method.

IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)•Dec 18, 2023•2 citations

Solving traveling salesman problems via a parallel fully connected ising machine

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.

ACM/IEEE Design Automation Conference (DAC)•Jul 10, 2022•21 citations

Penalty Coefficient Adjustment Technique for Extended Ising Machines

Fang Yin, Hirotaka Tamura, Yuki Furue +1 more

We have developed an extended Ising machine that extends the energy function, which is restricted to a binary-quadratic form in conventional Ising machines, to include a variety of penalty functions representing inequality constraints and higher-order energy terms. Such an extension opens up the possibility of dealing with problems featuring many (e.g., thousands or more) constraints. However, for problems with so many constraints, it is often necessary to adjust the value of the penalty coefficient, which represents the ratio of the penalty function to the total cost function, in order to find a solution. In this paper, we propose a penalty coefficient adjustment technique that can be combined with the parallel trial-based Exchange Monte Carlo method, a search algorithm for the extended Ising machine. The proposed algorithm enables us to solve the inequality constraint problem, which previously had the difficulty of manually determining penalty coefficients by trial and error. It also improves the solution quality. In two of the five QPLIB instances we tested, the extended Ising machine with fixed penalty coefficients obtained either a previous or a new best-known solution depending on the random seed, while the proposed coefficient adjustment method obtained a new best-known solution with all ten random seeds used.

IEEE Access•Jan 1, 2024•2 citations

Multi-Penalty Sample Persistence Variable Reduction for Constrained Combinatorial Optimization Problems

Shunta Ide, Shuta Kikuchi, Shu Tanaka

Ising machines, including quantum annealing machines, are promising for solving combinatorial optimization problems with high quality solutions. For constrained combinatorial optimization problems, choosing appropriate penalty coefficients is crucial for obtaining better feasible solutions. When tackling the large-scale combinatorial optimization problems, the variable reduction method is one of the most effective methods. To address these difficulties, we propose a new variable reduction method called multi-penalty sample persistence variable reduction (MP-SPVAR). The method is based on the sample persistence variable reduction method, and utilizes the solution samples across multiple penalty coefficients to fix the variables. The proposed method is evaluated on the 60-facility quadratic assignment problem tai60b from QAPLIB using an Ising machine. The experimental results show that MP-SPVAR can obtain better feasible solutions than solving the problem without any variable reduction. The proposed method is promising for solving the large-scale constrained combinatorial optimization problems with Ising machines.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Solving Traveling Salesman Problems Using Ising Models with Simulated Bifurcation

Tingting Zhang, Qichao Tao, Jie Han

Many combinatorial optimization problems can be solved by numerically simulating classical nonlinear Hamiltonian systems based on the Ising model. Solving the traveling salesman problem (TSP) using the Ising model requires a quadratically increasing number of spins with strict constraints. Unlike classical simulated annealing, simulated bifurcation (SB) can update the states of spins in parallel. This feature can potentially accelerate the convergence of Hamiltonian in the Ising model by taking advantage of modern multi-core processors. As an improved SB algorithm, the ballistic SB (bSB) algorithm is considered for solving the TSP in this paper. The TSP is converted to an Ising problem with external magnetic fields. bSB is then expanded by introducing a time-dependent factor. Experiments on benchmark datasets show that the bSB-based Ising solver offers superior performance in solution quality and convergence speed.

International SoC Design Conference•Oct 6, 2021•10 citations

Spin-Variable Reduction Method for Handling Linear Equality Constraints in Ising Machines

Tatsuhiko Shirai, Nozomu Togawa

We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.

IEEE Transactions on Computers•Jan 24, 2023•11 citations
When solving a combinatorial optimization problem with Ising machines, we have to formulate it onto an energy function of Ising model. Here, how to determine the penalty coefficients in the energy function is a great concern if it includes constraint terms. In this paper, we focus on a traveling salesman problem (TSP, in short), one of the combinatorial optimization problems with equality constraints. Firstly, we investigate the relationship between the penalty coefficient and the accuracy of solutions in a TSP. Based on it, we propose a method to obtain a TSP quasi-optimum solution, which is called multiple coefficients trial method. In our proposed method, we use an Ising machine to solve a TSP by changing a penalty coefficient every trial, the TSP solutions can converge very fast in total. Compared to naive methods using simulated-annealing-based Ising machines, we confirmed that our proposed method can reduce the total number of annealing iterations to 1/10 to 1/1000 to obtain a quasi-optimum solution in 32-city TSPs.
Ising machines have attracted much attention in recent years because of their potential in solving combinatorial optimization problems that are difficult to be solved using conventional computers. Ising machines solve the optimization problem that can be transformed into a quadratic unconstrained binary optimization (QUBO) problem. In the case of a problem with constraints, named a constraint problem, an objective function and constraint function with penalty coefficients are combined into a single Hamiltonian of a QUBO problem. When solving a constraint problem, the accuracy of the solution decreases compared to a QUBO problem with an objective function only. This is because penalty coefficients are set to excessively large values to prevent constraint violations. As a result, it becomes difficult to minimize the objective function. To solve this problem, this paper proposes a method that partitions constraint functions and reduces the value of the penalty coefficients. The performance evaluation using the traveling salesperson problem (TSP) with one-hot constraints demonstrates that the proposed method can improve the solution accuracy compared to the conventional method.
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.
We have developed an extended Ising machine that extends the energy function, which is restricted to a binary-quadratic form in conventional Ising machines, to include a variety of penalty functions representing inequality constraints and higher-order energy terms. Such an extension opens up the possibility of dealing with problems featuring many (e.g., thousands or more) constraints. However, for problems with so many constraints, it is often necessary to adjust the value of the penalty coefficient, which represents the ratio of the penalty function to the total cost function, in order to find a solution. In this paper, we propose a penalty coefficient adjustment technique that can be combined with the parallel trial-based Exchange Monte Carlo method, a search algorithm for the extended Ising machine. The proposed algorithm enables us to solve the inequality constraint problem, which previously had the difficulty of manually determining penalty coefficients by trial and error. It also improves the solution quality. In two of the five QPLIB instances we tested, the extended Ising machine with fixed penalty coefficients obtained either a previous or a new best-known solution depending on the random seed, while the proposed coefficient adjustment method obtained a new best-known solution with all ten random seeds used.
Ising machines, including quantum annealing machines, are promising for solving combinatorial optimization problems with high quality solutions. For constrained combinatorial optimization problems, choosing appropriate penalty coefficients is crucial for obtaining better feasible solutions. When tackling the large-scale combinatorial optimization problems, the variable reduction method is one of the most effective methods. To address these difficulties, we propose a new variable reduction method called multi-penalty sample persistence variable reduction (MP-SPVAR). The method is based on the sample persistence variable reduction method, and utilizes the solution samples across multiple penalty coefficients to fix the variables. The proposed method is evaluated on the 60-facility quadratic assignment problem tai60b from QAPLIB using an Ising machine. The experimental results show that MP-SPVAR can obtain better feasible solutions than solving the problem without any variable reduction. The proposed method is promising for solving the large-scale constrained combinatorial optimization problems with Ising machines.
Many combinatorial optimization problems can be solved by numerically simulating classical nonlinear Hamiltonian systems based on the Ising model. Solving the traveling salesman problem (TSP) using the Ising model requires a quadratically increasing number of spins with strict constraints. Unlike classical simulated annealing, simulated bifurcation (SB) can update the states of spins in parallel. This feature can potentially accelerate the convergence of Hamiltonian in the Ising model by taking advantage of modern multi-core processors. As an improved SB algorithm, the ballistic SB (bSB) algorithm is considered for solving the TSP in this paper. The TSP is converted to an Ising problem with external magnetic fields. bSB is then expanded by introducing a time-dependent factor. Experiments on benchmark datasets show that the bSB-based Ising solver offers superior performance in solution quality and convergence speed.
We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.