Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

Technical Summary: Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

Problem Statement
Ising machines serve as heuristic solvers for combinatorial optimization by searching for low-energy states of Ising or Quadratic Unconstrained Binary Optimization (QUBO) models. However, applying them directly to large-scale constrained problems (the "naive method") faces two primary difficulties:

1. Scalability: The number of binary variables in the QUBO formulation often exceeds the hardware capacity of current Ising machines.
2. Feasibility: Constraints are typically incorporated as penalty terms. Consequently, the search space includes infeasible solutions, and low-energy states do not necessarily correspond to high-quality feasible solutions of the original problem.

While existing approaches like variable fixing or divide-and-conquer attempt to reduce problem size, they often struggle to balance subproblem size with the ability to reconstruct feasible solutions for the original problem. Large Neighborhood Search (LNS) offers a framework where a feasible current solution is iteratively improved by re-optimizing a subproblem (a "neighborhood"). While LNS preserves feasibility if the subproblem generation method is designed correctly, the performance of Ising-machine-assisted LNS is highly sensitive to the size of the subproblem. If the subproblem is too small, the potential improvement per iteration is limited; if too large, the Ising machine's solution quality degrades due to the expanded search space.

Methodology
The paper focuses on two problems: the Vehicle Routing Problem (VRP) and the Quadratic Multiple Knapsack Problem (QMKP).

• Existing Method (LNS-V): For the VRP, the authors analyze a previous method (LNS-V) which selects a subset of vehicles and re-optimizes their entire routes. While this preserves feasibility, the subproblem size is controlled solely by the number of selected vehicles ($V'$). Because the entire route of a selected vehicle is re-optimized, the number of variables scales as $(V')^2(T-2)^2$ (where $T$ is the total steps). This results in coarse granularity; changing $V'$ by one can cause a massive jump in variable count, making it difficult to tune the subproblem size to the optimal range for the Ising machine.

• Proposed Method (LNS-VT): To address the granularity issue, the authors propose LNS-VT. In addition to selecting $V'$ vehicles, LNS-VT introduces a new parameter: the number of consecutive steps ($T'$) to be re-optimized for each selected vehicle.

  • Mechanism: For each selected vehicle, a contiguous segment of the route (of length $T_{seg} = \min(T', \text{actual valid steps})$) is extracted. The subproblem re-optimizes the assignment and order of sites within these specific segments while keeping the rest of the route fixed.
  • Feasibility: By fixing the sites outside the extraction intervals and ensuring the extracted segments only involve non-depot sites, the method guarantees that reinserting any feasible subproblem solution yields a feasible solution for the original VRP.
  • Variable Control: The number of free variables in LNS-VT is approximately $(V'T')^2$. This allows for fine-grained control over the subproblem size independent of the total problem steps $T$.

• Extension to QMKP: The authors apply the same design principle to the QMKP. They construct a subproblem generation method that selects a subset of knapsacks ($K'$) and a subset of items ($N'$) to re-optimize. This method also preserves feasibility by fixing items not in the selected set and adjusting capacity constraints for the residual capacity of the selected knapsacks.

Key Results
Numerical experiments were conducted using a 300-site, 5-vehicle VRP and a 200-item, 5-knapsack QMKP, utilizing the Fixstars Amplify AE Ising machine.

• VRP Performance:

  • LNS-VT outperformed both the naive method and the existing LNS-V.
  • The best LNS-VT setting (specifically $V'=2, T'=40$) reduced the objective value by approximately 10% relative to LNS-V after 100 iterations.
  • LNS-VT reached the final solution quality of LNS-V using only about 30% of the iterations.
  • Variable Sensitivity: The optimal subproblem size (in terms of non-depot site-assignment variables) was found to be between 6,000 and 10,000. The existing LNS-V could not achieve this range with $V' \ge 2$ (its minimum was ~14,400 variables), explaining its inferior performance.
  • Dynamic Needs: The appropriate subproblem size changed during the search process. Larger subproblems were more effective in early iterations (large objective values), while smaller subproblems were more effective in later iterations (refining high-quality solutions).

• QMKP Performance:

  • LNS applied to the QMKP also outperformed the naive method.
  • The optimal subproblem size for QMKP was found to be significantly smaller, approximately 100 to 150 variables.
  • This stark difference from the VRP (6,000–10,000) indicates that the optimal subproblem size is dependent on the specific problem class and QUBO formulation, not just the Ising machine's capabilities.

Significance and Claims
The paper claims that for Ising-machine-assisted LNS to be effective for large-scale constrained problems, feasibility preservation alone is insufficient. The ability to flexibly tune the subproblem size to match the Ising machine's performance sweet spot is a critical design factor.

The study demonstrates that:

1. Introducing an additional control parameter (consecutive steps for VRP, or item/knapsack counts for QMKP) allows for fine-grained adjustment of the subproblem size, which is impossible with methods that only vary the number of selected entities.
2. There exists an optimal range of variables for the subproblem that maximizes solution quality, and this range varies significantly between different problem classes (VRP vs. QMKP).
3. The optimal subproblem size may also depend on the quality of the current solution, suggesting that static parameter settings may not be optimal throughout the entire search process.

The authors conclude that while their results are specific to the tested instances and machine settings, the principle of structure-aware, flexibly tunable subproblem generation is a promising direction for constrained combinatorial optimization. They note that future work should focus on developing adaptive strategies to automatically select subproblem parameters based on the search stage and problem structure.