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

CREATORSHUNTA IDE 1, SHUTA KIKUCHI 2, 3, Shu Tanaka 1,2,3,4
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-19280

Browse the full library · About the Tower of Babel