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 International Conference on Quantum Computing and Engineering (QCE)

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

Shunta Ide, Shuta Kikuchi, Shu Tanaka

Published Aug 30, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/qce65121.2025.10413

Related papers

Extending Sample Persistence Variable Reduction for Constrained Combinatorial Optimization Problems

Shunta Ide, Kikuchi, Shuta, Shu Tanaka

Constrained combinatorial optimization problems (CCOPs) are challenging to solve due to the exponential growth of the solution space. When tackled with Ising machines, constraints are typically enforced by the penalty function method, whose coefficients must be carefully tuned to balance feasibility and objective quality. Variable-reduction techniques such as sample persistence variable reduction (SPVAR) can mitigate hardware limitations of Ising machines, yet their behavior on CCOPs remains insufficiently understood. Building on our prior proposal, we extend and comprehensively evaluate multi-penalty SPVAR (MP-SPVAR), which fixes variables using solution persistence aggregated across multiple penalty coefficients. Experiments on benchmark problems, including the quadratic assignment problem and the quadratic knapsack problem, demonstrate that MP-SPVAR attains higher feasible-solution ratios while matching or improving approximation ratios relative to the conventional SPVAR algorithm. An examination of low-energy states under small penalties clarifies when feasibility degrades and how encoding choices affect the trade-off between solution quality and feasibility. These results position MP-SPVAR as a practical variable-reduction strategy for CCOPs and lay a foundation for systematic penalty tuning, broader problem classes, and integration with quantum-inspired optimization hardware as well as quantum algorithms.

arXiv:2509.19280•Sep 23, 2025•0 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

Variable Reduction Method for Quadratic Three-Dimensional Assignment Problem with FMQA

Sora Tomita, Tatsuhiko Shirai, Nozomu Togawa

Ising machines including quantum annealers have attracted attention as efficient solvers for combinatorial optimization problems (COPs). To use Ising machines, the objective function and constraints of a COP must be expressed in a QUBO (quadratic unconstrained binary optimization) form. However, their application range is practically limited since some COPs are difficult to formulate in a QUBO form, or require a large number of binary variables. Quadratic three-dimensional assignment problem (Q3AP) is a challenging problem for Ising machines to solve since the number of required binary variables rapidly increases with the problem size N. In this paper, to overcome the difficulty, we propose a method to reduce the number of necessary variables from$N^{3}$to$2N^{2}$by using a factorization machine with quantum annealing (FMQA) to estimate QUBO through machine learning. Experimental results with a real Ising machine demonstrate that the proposed method can obtain the best-known solution in a short time.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 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

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

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
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.
Constrained combinatorial optimization problems (CCOPs) are challenging to solve due to the exponential growth of the solution space. When tackled with Ising machines, constraints are typically enforced by the penalty function method, whose coefficients must be carefully tuned to balance feasibility and objective quality. Variable-reduction techniques such as sample persistence variable reduction (SPVAR) can mitigate hardware limitations of Ising machines, yet their behavior on CCOPs remains insufficiently understood. Building on our prior proposal, we extend and comprehensively evaluate multi-penalty SPVAR (MP-SPVAR), which fixes variables using solution persistence aggregated across multiple penalty coefficients. Experiments on benchmark problems, including the quadratic assignment problem and the quadratic knapsack problem, demonstrate that MP-SPVAR attains higher feasible-solution ratios while matching or improving approximation ratios relative to the conventional SPVAR algorithm. An examination of low-energy states under small penalties clarifies when feasibility degrades and how encoding choices affect the trade-off between solution quality and feasibility. These results position MP-SPVAR as a practical variable-reduction strategy for CCOPs and lay a foundation for systematic penalty tuning, broader problem classes, and integration with quantum-inspired optimization hardware as well as quantum algorithms.
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 annealers have attracted attention as efficient solvers for combinatorial optimization problems (COPs). To use Ising machines, the objective function and constraints of a COP must be expressed in a QUBO (quadratic unconstrained binary optimization) form. However, their application range is practically limited since some COPs are difficult to formulate in a QUBO form, or require a large number of binary variables. Quadratic three-dimensional assignment problem (Q3AP) is a challenging problem for Ising machines to solve since the number of required binary variables rapidly increases with the problem size N. In this paper, to overcome the difficulty, we propose a method to reduce the number of necessary variables fromN3N^{3}N3to2N22N^{2}2N2by using a factorization machine with quantum annealing (FMQA) to estimate QUBO through machine learning. Experimental results with a real Ising machine demonstrate that the proposed method can obtain the best-known solution in a short time.
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.
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.
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.