Extending Sample Persistence Variable Reduction for Constrained Combinatorial Optimization Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915586208956416 |
|---|---|
| author | Ide, Shunta Kikuchi, Shuta Tanaka, Shu |
| author_facet | Ide, Shunta Kikuchi, Shuta Tanaka, Shu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_19280 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Extending Sample Persistence Variable Reduction for Constrained Combinatorial Optimization Problems Ide, Shunta Kikuchi, Shuta Tanaka, Shu Statistical Mechanics 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. |
| title | Extending Sample Persistence Variable Reduction for Constrained Combinatorial Optimization Problems |
| topic | Statistical Mechanics |
| url | https://arxiv.org/abs/2509.19280 |