aiqbench analysis
This research investigates how geometric structures inherent in vehicle routing solutions influence the performance of Ising-machine-assisted large neighborhood search algorithms. The study demonstrates that preserving spatial relationships during subproblem formulation yields superior optimization results compared to methods relying solely on variable counts or constraint relations. This work advances practical strategies for scaling combinatorial solvers by leveraging physical insights from disordered systems and neural networks within quantum hardware constraints.
Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search
arXiv:2607.05014v2 Announce Type: replace-cross Abstract: Large-scale quadratic unconstrained binary optimization (QUBO) formulations of constrained combinatorial optimization problems often exceed the input-size limit of present Ising machines or suffer from degraded solution quality as the number of binary variables increases. Large neighborhood search (LNS) mitigates this difficulty by sequentially optimizing restricted subproblems, but the structural factors that distinguish subproblems beyond the number of binary variables remain insufficiently characterized. In this study, we examine vehicle routing problems and compare a construction based on the vehicle routes of the current solution, denoted by LNS-K, with a construction based on QUBO variables and constraint relations, denoted by LNS-Q, while controlling the number of binary variables in the subproblems. Under the tested conditions, LNS-K obtained shorter total distances than LNS-Q in the matched-size comparisons, and the position variance, a measure of the spatial spread of the selected customers, decreased during the iterations in LNS-K. These observations suggest that subproblem design for sequential optimization with Ising machines should consider not only subproblem size but also semantic and geometric structures inherited from the current solution.
Abstract:Large-scale quadratic unconstrained binary optimization (QUBO) formulations of constrained combinatorial optimization problems often exceed the input-size limit of present Ising machines or suffer from degraded solution quality as the number of binary variables increases. Large neighborhood search (LNS) mitigates this difficulty by sequentially optimizing restricted subproblems, but the structural factors that distinguish subproblems beyond the number of binary variables remain insufficiently characterized. In this study, we examine vehicle routing problems and compare a construction based on the vehicle routes of the current solution, denoted by LNS-K, with a construction based on QUBO variables and constraint relations, denoted by LNS-Q, while controlling the number of binary variables in the subproblems. Under the tested conditions, LNS-K obtained shorter total distances than LNS-Q in the matched-size comparisons, and the position variance, a measure of the spatial spread of the selected customers, decreased during the iterations in LNS-K. These observations suggest that subproblem design for sequential optimization with Ising machines should consider not only subproblem size but also semantic and geometric structures inherited from the current solution.
Statistical Mechanics (cond-mat.stat-mech); Disordered Systems and Neural Networks (cond-mat.dis-nn); Quantum Physics (quant-ph)
arXiv:2607.05014 [cond-mat.stat-mech]
(or arXiv:2607.05014v2 [cond-mat.stat-mech] for this version)
https://doi.org/10.48550/arXiv.2607.05014 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 274 words
Related coverage
Machine Learning-Enhanced Tabu Search for Tactical Wireless Network Design
arXiv · Sep 1, 2026
Order Parameter Discovery for Quantum Many-Body Systems
Quantum Journal · Sep 29, 2026
Presentation: From Models to Agents: Building Context-Aware Consumer AI at Scale at DoorDash
InfoQ · Aug 15, 2026
GeoNest: Learning to Select Failure-Aware Neighborhoods for the Irregular Knapsack Problem in a Circular Container
arXiv · Oct 1, 2026