arXiv:2509.19280

Extending Sample Persistence Variable Reduction for Constrained Combinatorial Optimization Problems

Shunta Ide, Kikuchi, Shuta, Shu Tanaka

Published Sep 23, 2025• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2509.19280

Related papers

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, 20250 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 ComputersJan 24, 202311 citations

CVaR-Assisted Custom Penalty Function for Constrained Optimization

Xin Wei Lee, Hoong Chuin Lau

We propose a slack-free penalty formulation for constrained binary optimization that eliminates auxiliary slack variables and preserves the feasibility structure of the original problem. The proposed approach introduces a nonlinear custom penalty function to enforce inequality constraints directly in the objective function. To address the computational challenges associated with evaluating nonlinear penalties in variational quantum algorithms, we employ the finite-sampling method that avoids the exponential complexity required by exact expectation computation. Furthermore, we integrate the Conditional Value-at-Risk (CVaR) objective to improve optimization robustness and guide the search toward high-quality solutions. The proposed framework is evaluated on instances of the multi-dimensional knapsack problem, a classical benchmark in combinatorial optimization. We showcase that the proposed custom-penalty formulation combined with CVaR sampling achieves improved optimality gaps and more consistent performance compared with conventional slack-based QUBO formulations. We also tested our method on the Quantinuum H2 quantum hardware, demonstrating the possibilities of training small-sized VQE on noisy trapped-ion quantum computers. The results suggest that careful penalty design can play a critical role in enabling quantum and hybrid quantum-classical algorithms for constrained optimization problems that arise in operations research.

quant-pharXiv:2604.20088Apr 23, 20260 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, 20251 citation

QUBO Formulations and Characterization of Penalty Parameters for the Multi-Knapsack Problem

Evren Güney, Joachim C.F. Ehrenthal, Thomas Hanne

The Multi-Knapsack Problem (MKP) is a fundamental challenge in operations research and combinatorial optimization. Quantum computing introduces new possibilities for solving MKP using Quadratic Unconstrained Binary Optimization (QUBO) models. However, a key challenge in QUBO formulations is the selection of penalty parameters, which directly influence solution feasibility and algorithm performance. In this work, we develop QUBO formulations for two MKP variants—the Multidimensional Knapsack Problem (MDKP) and the Multiple Knapsack Problem (MUKP)—and provide an algebraic characterization of their penalty parameters. We systematically evaluate their impact through quantum simulation experiments and compare the performance of the two leading quantum optimization approaches: Quantum Approximate Optimization Algorithm (QAOA) and quantum annealing, alongside a state-of-the-art classical solver. Our results indicate that while classical solvers remain superior, careful tuning of penalty parameters has a strong impact on quantum optimization outcomes. QAOA is highly sensitive to parameter choices, whereas quantum annealing produces more stable results on small to mid-sized instances. Further, our results reveal that MDKP instances can maintain feasibility at penalty values below theoretical bounds, while MUKP instances show greater sensitivity to penalty reductions. Finally, we outline directions for future research in solving MKP, including adaptive penalty parameter tuning, hybrid quantum-classical approaches, and practical optimization strategies for QAOA, as well as real-hardware evaluations.

IEEE AccessJan 1, 20257 citations

Constraint-Parameterized Spin-Variable Reduction Method for QAP

Raio Aoki, Takeru Ota, Tatsuhiko Shirai +1 more

Developing novel quadratic unconstrained binary optimization (QUBO) formulations is important to enhance the performance of the Ising machines. The spin-variable reduction (SVR) method formulates the QUBO with fewer binary variables than the penalty method. However, the SVR method can complicate the energy landscape. To address this issue, we propose a constraint-parameterized SVR method for the combinatorial optimization problems with a 2-way 1-hot constraint such as the quadratic assignment problem (QAP). Our proposed method introduces two key elements: (1) preliminary analysis using simulated annealing (SA) to statistically identify the variable that has a high probability of being the value of 1, and (2) parameterization of the SVR constraint term using this statistical information. Experiments on QAP benchmarks show that our method can find higher-precision solutions more efficiently than conventional SVR or the penalty method in certain cases.

International Conference on Consumer ElectronicsFeb 3, 20260 citations