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

IEEE Access

Penalty Coefficient Adjustment Technique for Extended Ising Machines

Fang Yin, Hirotaka Tamura, Yuki Furue, Yasuhiro Watanabe

Published Jan 1, 2024• 2 citations
Publisher

Abstract

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.

DOI
10.1109/access.2024.3494736

Related papers

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

Takehara Kota, Daisuke Oku, Yoshiki Matsuda +2 more

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.

International Conference on Consumer Electronics•Sep 8, 2019•9 citations

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

Techniques to enhance a QUBO solver for permutation-based combinatorial optimization

Siong Thye Goh, Jianyuan Bo, Sabrish Gopalakrishnan +1 more

Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•10 citations

Constraint Coefficient Tuning of Spin-Variable Reduction for QAP

Raio Aoki, Tatsuhiko Shirai, Nozomu Togawa

Ising machines, including quantum annealers, have attracted much attention as an efficient solver for COPs (Combinatorial optimization problems). The SVR (Spin-Variable Reduction) method maps a COP with linear equality constraints to QUBO (Quadratic Unconstrained Binary Optimization) model, which is a common input for using the Ising machines. In this paper, we conduct a tuning of a constraint coefficient for this method using Quadratic Assignment Problems as a case study. We find that the optimal value of the constraint coefficient can be either larger or smaller than that used in the conventional penalty method, depending on the problem instance. We discuss the underlying mechanism responsible for this difference.

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

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

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
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.
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.
Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.
Ising machines, including quantum annealers, have attracted much attention as an efficient solver for COPs (Combinatorial optimization problems). The SVR (Spin-Variable Reduction) method maps a COP with linear equality constraints to QUBO (Quadratic Unconstrained Binary Optimization) model, which is a common input for using the Ising machines. In this paper, we conduct a tuning of a constraint coefficient for this method using Quadratic Assignment Problems as a case study. We find that the optimal value of the constraint coefficient can be either larger or smaller than that used in the conventional penalty method, depending on the problem instance. We discuss the underlying mechanism responsible for this difference.
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.
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.