Extending Sample Persistence Variable Reduction for Constrained Combinatorial Optimization Problems
SHUNTA IDE 1, SHUTA KIKUCHI 2, 3, Shu Tanaka 1,2,3,4 · 2025
Read Extending Sample Persistence Variable Reduction for Constrained Combinatorial Optimization Problems by SHUNTA IDE 1, SHUTA KIKUCHI 2, 3, Shu Tanaka 1,2,3,4 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-19280.txt.
Description
Hard combinatorial problems with constraints, like assigning jobs or packing knapsacks, strain the Ising machines built to solve them. Shunta Ide and two co-authors improve a trick called sample persistence variable reduction, which fixes some variables early based on repeated solutions. Constraints are usually enforced with penalty terms, whose strength is a delicate dial. Their extension gathers persistence across several penalty settings at once, rather than trusting one.
On benchmark assignment and knapsack problems, the multi-penalty version found feasible solutions more often than the classic method. Its solution quality matched or beat the classic as well. Studying low-energy states under weak penalties clarifies when feasibility breaks and how encoding choices shift the trade-off. The authors position the method as a practical tool for constrained problems on quantum-inspired hardware, and a foundation for systematic penalty tuning.
Catalog record
| CREATOR | SHUNTA IDE 1, SHUTA KIKUCHI 2, 3, Shu Tanaka 1,2,3,4 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-19280