Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search

Technical Summary: Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search

Problem Statement
Large-scale constrained combinatorial optimization problems, such as the Vehicle Routing Problem (VRP), often require Quadratic Unconstrained Binary Optimization (QUBO) formulations that exceed the input-size limits of current Ising machines or suffer from degraded solution quality as the number of binary variables increases. While Large Neighborhood Search (LNS) mitigates this by sequentially optimizing restricted subproblems, existing approaches primarily treat the number of binary variables as the sole control parameter. The authors posit that the number of variables alone is insufficient to characterize a subproblem; different construction rules can yield distinct internal structures, constraint relations, and geometric distributions even when variable counts are identical. The central question is whether the subproblem construction rule affects the sequential optimization process when the subproblem size (number of binary variables) is held fixed.

Methodology
The study investigates this question using the VRP as a testbed, comparing two distinct subproblem construction rules within an Ising-machine-assisted LNS framework:

1. LNS-K (Route-Structure-Based): This method constructs subproblems based on the semantic units of the VRP. It selects a subset of vehicles ($K'$) from the current solution and includes all customers visited by those vehicles. The subproblem variables correspond to the routes of the selected vehicles and their associated customers.
2. LNS-Q (QUBO-Variable-Based): This method constructs subproblems based on the QUBO representation. It selects a subset of active binary variables ($n'$) from the current solution as "anchors" and includes all variables involved in the constraints associated with these anchors. This approach operates at the representation level rather than the problem-domain level.

The authors utilized two Ising machines: the D-Wave Advantage 4.1 (quantum annealing) for small-scale instances ($N=5, 6, 7$) and the Fixstars Amplify AE (GPU-based) for large-scale instances ($N=100, 200, 300, 400$).

The experimental protocol involved two main comparisons:

• LNS vs. Naive Approach: Comparing sequential LNS against a single-shot submission of the full QUBO, matched by total annealing time.
• LNS-K vs. LNS-Q: A "matched-size" comparison where parameters $K'$ and $n'$ were tuned so that both methods generated subproblems with the exact same number of binary variables.

Key metrics included the total distance of the solution, the iterative improvement trajectory, and the position variance of the selected customer set (a measure of the spatial spread of customers included in the subproblem).

Key Results

1. Sequential Optimization Efficacy: Under matched total annealing-time budgets, LNS consistently outperformed the naive approach (single-shot full QUBO) across both hardware platforms and problem sizes. LNS maintained feasible solutions throughout the process and achieved significantly shorter total distances, particularly for larger instances ($N=400$).
2. Impact of Construction Rules: Even when the number of binary variables in the subproblems was strictly matched, LNS-K and LNS-Q exhibited different optimization behaviors.
   • Final Solution Quality: LNS-K achieved shorter final total distances than LNS-Q across the tested parameter ranges for the 400-customer instance.
   • Iterative Trajectories: LNS-K demonstrated faster iterative improvement, particularly for smaller matched subproblem sizes ($K'=2, 3$).
3. Geometric Evolution: A critical finding concerns the spatial distribution of selected customers.
   • In LNS-K, the position variance of the selected customer set decreased significantly during iterations, indicating that the algorithm progressively focused on more spatially localized clusters of customers as the solution improved.
   • In LNS-Q, the position variance remained nearly constant throughout the iterations, regardless of the subproblem size.

Significance and Claims
The paper claims that the number of binary variables is an insufficient descriptor for subproblems in Ising-machine-assisted sequential optimization. The study demonstrates that the construction rule itself—specifically, whether variables are grouped by semantic problem-domain units (routes) or by QUBO constraint relations—fundamentally shapes the optimization trajectory and final solution quality.

The authors argue that subproblem design must consider not only size but also the semantic and geometric structures inherited from the current solution. The superior performance of LNS-K suggests that preserving the route structure of the current solution allows the algorithm to exploit spatial locality, leading to more effective local rearrangements.

Limitations and Scope
The authors explicitly note several limitations:

• The conclusions are specific to the tested VRP instances and the particular QUBO formulation used.
• The geometric analysis is descriptive; the paper does not establish a causal link between the decrease in position variance and the improvement in total distance, nor does it claim that spatial localization is the sole cause of LNS-K's success.
• The detailed structure comparison was performed primarily on the Fixstars Amplify AE platform; the results are not claimed to be hardware-independent.
• The study does not provide a comprehensive benchmark against state-of-the-art classical vehicle routing heuristics, focusing instead on the internal mechanics of Ising-machine-assisted LNS.

In conclusion, the paper posits that effective subproblem design for Ising machines requires integrating structural information from the current solution, moving beyond simple variable-count constraints.