Pith. sign in

REVIEW 3 major objections 7 minor 67 references

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

T0 review · 3 major / 7 minor · reviewed 2026-07-08 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Finely Tunable Subproblem Size Improves Ising Machine Routing

desk verdict LNS-VT adds a segment-length parameter to feasibility-preserving LNS for Ising machines — clean construction, sound feasibility argument, but empirical evidence rests on one VRP instance and one QMKP instance. read the letter →

arxiv 2607.05169 v1 pith:LC7QOWMW submitted 2026-07-06 cond-mat.stat-mech

Koshiro Fujimoto , Masashi Yamashita , Shu Tanaka This is my paper
classification cond-mat.stat-mech
keywords IsingmachinelargeneighborhoodsearchvehicleroutingproblemquadraticmultipleknapsackQUBOcombinatorialoptimizationsubproblemgenerationfeasibilitypreservation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Ising machines struggle when large constrained optimization problems are fed to them as a single QUBO because the search space becomes too large for the machine to find good solutions. Large neighborhood search (LNS) addresses this by iteratively re-optimizing small parts of a feasible solution. The existing method for vehicle routing, LNS-V, selects whole vehicles and re-optimizes their entire routes, which means the subproblem size jumps in coarse increments tied to route length. The paper proposes LNS-VT, which adds a second parameter: the number of consecutive steps to re-optimize per selected vehicle. This lets the subproblem size be tuned to any value, independent of the original problem size, while preserving feasibility. On a 300-site, 5-vehicle VRP, the best LNS-VT setting reduced the objective by about 10% relative to LNS-V after 100 iterations and reached LNS-V's final quality in about 30 iterations. The same design principle applied to the quadratic multiple knapsack problem also showed an optimal subproblem-size window, though at a much smaller variable count than for VRP. The central finding is that feasibility preservation alone is insufficient; the ability to place the subproblem size in the Ising machine's quality sweet spot matters, and that sweet spot shifts as the solution improves.

What carries the argument

LNS-VT

What would settle it

If the 10% improvement of LNS-VT over LNS-V disappears or reverses on VRP instances with different site distributions, different numbers of vehicles, or different route lengths, the central claim that fine-grained subproblem-size control is beneficial would not hold broadly.

Watch

Extended reading notes

Core claim

The paper introduces LNS-VT, a subproblem generation method for Ising-machine-assisted large neighborhood search on the vehicle routing problem. By parameterizing not just how many vehicles to re-optimize but also how many consecutive steps of each vehicle's route to re-optimize, LNS-VT decouples subproblem size from the original problem's step count while guaranteeing that reinsertion always produces a feasible solution. The key empirical finding is that there exists an optimal subproblem-size window (approximately 6000-10000 variables for the tested VRP, 100-150 for the tested QMKP) where the Ising machine returns its best solutions, and that this window is inaccessible to the existing LNS

Load-bearing premise

The claim that LNS-VT outperforms LNS-V rests on a single VRP instance with 300 uniformly random sites and a single QMKP benchmark instance, both run on one specific Ising machine backend, so the observed 10% improvement and the identified sweet-spot ranges could be artifacts of these particular instances and settings.

Editorial extensions

If this is right

  • Adaptive LNS strategies that shrink the subproblem size as the solution improves could automatically exploit the observed shift in the optimal size window, potentially without requiring parameter sweeps.
  • The design principle of adding a tunable granularity parameter to feasibility-preserving subproblem generation could extend to other constrained combinatorial problems beyond VRP and QMKP, such as scheduling or graph coloring.
  • If the optimal subproblem-size window can be predicted from QUBO structure or constraint density rather than measured empirically, deployment of Ising-machine-assisted LNS would become significantly more practical.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The fact that the optimal subproblem size differs by roughly two orders of magnitude between VRP and QMKP suggests the sweet spot may correlate with properties of the QUBO interaction graph, such as degree or clustering, rather than with problem semantics.
  • The observation that larger subproblems help early (when improvements are large) and smaller ones help later (when precision matters) resembles a temperature schedule in simulated annealing, hinting at a possible connection between subproblem size and effective search temperature.
  • If the Ising machine's solution quality degrades smoothly with variable count, one could in principle estimate the quality-vs-size curve from a small calibration run and then select subproblem sizes analytically rather than by exhaustive testing.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 7 minor

Summary. This paper proposes LNS-VT, a subproblem generation method for Ising-machine-assisted large neighborhood search (LNS) applied to the vehicle routing problem (VRP). LNS-VT extends the existing LNS-V method by introducing a prescribed segment length T' that controls how many consecutive steps of each selected vehicle's route are re-optimized, enabling finer control of subproblem size while preserving feasibility. The authors prove that LNS-VT is feasibility-preserving and demonstrate on a 300-site, 5-vehicle VRP instance that the best LNS-VT setting (V'=2, T'=40) reduces the average objective by approximately 10% relative to LNS-V after 100 iterations. The same design principle is applied to the quadratic multiple knapsack problem (QMKP), where an appropriate subproblem size range is also identified. The feasibility-preservation argument (Sec. 3.3) is clean: extraction intervals lie within the non-depot part of each route, so constraints B, C, D are inherited from the current solution, and the penalty terms in Eq. (26) enforce constraint A. The QUBO formulations are standard. The central methodological contribution—finer subproblem-size control while preserving feasibility—is sound.

Significance. The paper addresses a genuine practical limitation of Ising-machine-assisted LNS: the inability to place subproblem sizes in the range where the solver achieves good solution quality. The LNS-VT construction is a natural and well-motivated extension of LNS-V, and the feasibility-preservation argument is rigorous. The observation that the appropriate subproblem size shifts with solution quality (Sec. 5.1, Fig. 4) is an interesting empirical finding. The QMKP extension (Sec. 6) demonstrates that the design principle generalizes beyond the VRP, though it also rests on a single benchmark instance. The paper ships falsifiable predictions (the sweet-spot ranges for VRP and QMKP) and is transparent about the limitations of single-instance testing (Sec. 7). The methodological contribution holds regardless of whether the specific empirical improvements generalize broadly.

major comments (3)
  1. Sec. 4.1, Table I: The central empirical claim—that LNS-VT with V'=2, T'=40 reduces the average objective by ~10% relative to LNS-V after 100 iterations—rests on a single VRP instance (300 sites, 5 vehicles, uniformly random in a unit square) and a single common initial solution. The paper acknowledges this in Sec. 7. Two aspects make this more than a generic concern. First, the identified sweet-spot range of 6000–10000 variables (Fig. 3) is used to explain why LNS-VT outperforms LNS-V (whose minimum subproblem size is 14400 variables per Eq. 30). If this sweet-spot range shifts or vanishes on other instances—due to different site distributions, vehicle counts, or route structures—the explanatory mechanism and practical recommendation both weaken. Second, all LNS runs start from the same initial solution, so the observed advantage could partly reflect the specific structure of that one初始
  2. Sec. 4.1: The penalty coefficients for all QUBOs (full and subproblem) are set to l_max = max_{i,j} l_{i,j} without instance-specific or subproblem-specific recomputation. While this is a standard heuristic (Ref. 6), the paper does not report the empirical feasible-solution rate for subproblem QUBOs specifically—only that the final reinserted solutions were 100% feasible. If the Ising machine frequently returns subproblem-infeasible solutions (which are then discarded per Algorithm 1, line 5), the effective number of useful iterations could be much lower than 100, which would affect the comparison between LNS-VT and LNS-V. Reporting the subproblem-feasible rate for each setting would strengthen the empirical analysis.
  3. Sec. 4.2, Fig. 2: The comparison between LNS-VT and LNS-V uses the same computation time per QUBO (10 s) and the same number of iterations (100). However, the subproblem generation overhead (vehicle selection, extraction interval sampling, QUBO construction) is not included in the timing. For LNS-VT, the QUBO construction is more complex than for LNS-V (cf. Eq. 25 vs. Eq. 12), and this overhead may not be negligible relative to 10 s. The paper should clarify whether this overhead is included and, if not, discuss its potential impact on the comparison.
minor comments (7)
  1. Ref. 56 (Yamashita and Tanaka, 2026) is cited as a preprint with placeholder arXiv ID 'arXiv:2607.xxxxx'. This should be updated with the correct identifier.
  2. Sec. 6.4, Eq. (53): The number of auxiliary variables in Fig. 8 is 'formally unified' with that of the original problem (D_k rather than D'_k), which is an approximation. The text notes this does not deviate significantly, but no quantitative bound is given. A brief statement of the maximum discrepancy would improve transparency.
  3. Fig. 3: The horizontal axis spans 0–15000 variables, but the key data points cluster in the 2500–15000 range. The empty space below 2500 makes the figure hard to read. Consider adjusting the axis range.
  4. Sec. 5.2, Fig. 5: The auxiliary experiment uses N=120 sites (different from the main experiment's N=300) and solves the full QUBO directly. The connection between this experiment and the V'-dependence observed in Fig. 3 is indirect. The text is careful about this, but a brief note that this experiment provides only indirect evidence would help.
  5. Sec. 3.3, Eq. (24): The definitions of a_v and b_v reference r^{(m)}_v(T^{(v)}_0 - 1) and r^{(m)}_v(T^{(v)}_0 + T_seg), but the case where T^{(v)}_0 = 1 (so a_v = r^{(m)}_v(0) = depot) is not explicitly discussed. The text mentions 'The site a_v or b_v can be the depot,' but confirming that the indexing is well-defined at the boundary would improve clarity.
  6. Table II: The naive method is given 300 s of computation time, while each LNS run gets 100 × 10 s = 1000 s total. The text notes this is not a wall-clock-time comparison, but the table format makes this easy to miss. A footnote or explicit statement in the table caption would help.
  7. Sec. 6.3: The penalty coefficients for QMKP are set to μ_E = N and μ_F = 100N, selected from preliminary trials. No sensitivity analysis is provided. A brief note on how robust the results are to these choices would strengthen the QMKP results.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for a careful and constructive report. The referee correctly identifies the central methodological contribution (finer subproblem-size control with feasibility preservation) as sound, and raises three major comments, all concerning empirical robustness and reporting: (1) the central ~10% improvement claim rests on a single VRP instance and a single initial solution; (2) the subproblem-feasible rate for subproblem QUBOs is not reported; (3) subproblem generation overhead is not included in the timing. We agree with all three points and will revise the manuscript accordingly. None of the revisions affect the methodological contribution or the feasibility-preservation argument.

read point-by-point responses

  1. Referee: Sec. 4.1, Table I: The central empirical claim rests on a single VRP instance and a single common initial solution. The sweet-spot range could shift or vanish on other instances, and the observed advantage could partly reflect the specific structure of that one initial solution.

    Authors: The referee is correct on both points. The manuscript already acknowledges in Sec. 7 that the conclusions are based on the tested instances and Ising-machine settings, but the current acknowledgment is too brief and does not explicitly address the two specific risks the referee identifies: (i) that the sweet-spot range of 6000–10000 variables may shift or vanish under different site distributions, vehicle counts, or route structures, and (ii) that the use of a single common initial solution means the observed advantage could partly reflect the structure of that particular solution. We will revise Sec. 7 to state these two limitations explicitly and to clarify that the explanatory mechanism (LNS-V's minimum subproblem size of 14400 variables exceeding the sweet-spot range) is instance-dependent in the sense that the sweet-spot range itself was measured on one instance. We will also add a sentence in Sec. 4.1 noting that all runs share a single initial solution and that this is a limitation of the experimental design. We fully agree that multi-instance experiments with multiple initial solutions would be needed to establish the generality of the ~10% improvement and the sweet-spot range. However, conducting such experiments within the revision period is not feasible because each LNS run requires 1000 s of Ising-machine computation time per setting, and the parameter sweep already involves 18 settings. We will therefore be transparent that the empirical claim is instance-specific and frame the ~10% figure as an illustration of the mechanism rather than a generalizable performance guarantee. The methodological contribution—finer subproblem-size control while preserving feasibility—does not depend on the generality of this specific empirical result. revision: yes

  2. Referee: Sec. 4.1: The penalty coefficients are set to l_max without instance-specific or subproblem-specific recomputation, and the subproblem-feasible rate for subproblem QUBOs is not reported. If the Ising machine frequently returns subproblem-infeasible solutions, the effective number of useful iterations could be much lower than 100.

    Authors: We agree that reporting the subproblem-feasible rate is important and that its absence is a genuine gap in the empirical analysis. To clarify the current status: the manuscript states (Sec. 4.2) that 'the empirical feasible-solution rate was 100% for the naive method, LNS-V, and LNS-VT,' but this refers to the feasibility of the final reinserted solutions, not to the subproblem-feasible rate at the QUBO level. The referee is correct that these are different quantities. In our experiments, the Ising machine (Fixstars Amplify AE) returned multiple candidate solutions per QUBO solve, and the algorithm selects the best subproblem-feasible one (Algorithm 1, line 5). We will add the subproblem-feasible rate—i.e., the fraction of iterations in which at least one subproblem-feasible solution was obtained from the Ising machine's output—for each LNS-VT and LNS-V setting. We have the raw data from the experiments and can compute this rate for each parameter setting. We will add a table or sentence in Sec. 4.2 reporting these rates. If the rates differ substantially between LNS-VT and LNS-V, this would indeed affect the interpretation of the comparison, and we will discuss this. If the rates are uniformly high (which we expect based on the 100% final-feasibility observation, since infeasible subproblem solutions are discarded), we will state so explicitly. revision: yes

  3. Referee: Sec. 4.2, Fig. 2: The subproblem generation overhead (vehicle selection, extraction interval sampling, QUBO construction) is not included in the timing. For LNS-VT, the QUBO construction is more complex than for LNS-V, and this overhead may not be negligible relative to 10 s.

    Authors: The referee is correct that the subproblem generation overhead is not included in the 10 s per-QUBO computation time reported in Table II, and that LNS-VT's QUBO construction (Eq. 25) is more complex than LNS-V's (Eq. 12). We will clarify in Sec. 4.1 and Table II that the 10 s refers to the Ising-machine solve time only and does not include subproblem generation overhead (vehicle selection, extraction interval sampling, QUBO construction, and reinsertion). We will also add a brief discussion of the overhead's potential impact. In our implementation, the subproblem generation and QUBO construction are performed on a classical CPU and are dominated by matrix assembly for the QUBO. For the subproblem sizes in our experiments (at most 14400 site-assignment variables), this overhead is on the order of seconds or less, which is small relative to the 10 s Ising-machine solve time but not strictly negligible. We will state this qualitatively. We note that a precise end-to-end wall-clock-time comparison would require specifying the hardware, implementation language, and parallelization strategy, which is beyond the scope of the current manuscript. The manuscript already states (Sec. 4.2) that the comparison 'does not by itself establish an end-to-end wall-clock-time advantage,' and we will reinforce this caveat in the revised text. revision: yes

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the paper is self-contained with one minor self-citation used as a comparison baseline.

full rationale

The paper's central contribution — the LNS-VT subproblem generation method — is defined constructively in Algorithm 2 and Eqs. (17)-(28). The feasibility-preservation argument (Sec. 3.3) follows directly from the construction: variables outside the extraction intervals are fixed to the current solution, so constraints A-D of the original VRP are inherited. This is a straightforward structural argument, not a circular one. The subproblem-size formula n_var = (V'T_seg)^2 (Eq. 27) is derived from counting free variables in the construction, not fitted to data. The empirical claim of ~10% improvement over LNS-V (Sec. 4.2) is an experimental observation on a specific VRP instance, not a prediction derived from a fitted parameter. The sweet-spot range of 6000-10000 variables (Fig. 3) is observed empirically, not predicted from theory. The QMKP extension (Sec. 6) constructs an independent subproblem generation method with its own feasibility proof. The only self-citation is Ref. 56 (Yamashita and Tanaka, 2026), which defines LNS-V — the comparison baseline. This citation is not load-bearing for LNS-VT's construction or its feasibility argument; it is used only to identify the baseline method and its subproblem-size limitation (Eq. 16). The paper is self-contained against its external benchmarks (Fixstars Amplify AE, standard QKP benchmark instance). Score 1 reflects the minor self-citation that does not affect the paper's independent content.

Assumptions & free parameters 6 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new physical entities, particles, forces, or dimensions. It introduces algorithmic parameters (V', T', K', N') which are design choices, not postulated physical objects. The QUBO formulations use standard binary variables and penalty terms. The free parameters are all empirically tuned control knobs, not fitted constants in a derivation.

free parameters (6)
  • V' (number of selected vehicles) = 2 (best for VRP); 2-5 (tested)
    Controls how many vehicles are included in the subproblem. Selected empirically by parameter sweep.
  • T' (prescribed segment length) = 40 (best for VRP with V'=2); 10-50 (tested)
    Controls the number of consecutive steps re-optimized per vehicle. The key new parameter introduced by LNS-VT. Selected empirically.
  • K' (number of selected knapsacks, QMKP) = 2-5 (tested)
    Controls how many knapsacks are in the QMKP subproblem. Selected empirically.
  • N' (prescribed number of items, QMKP) = 10-40 (tested)
    Controls how many items are in the QMKP subproblem. Selected empirically.
  • µ_A, µ_B, µ_C (VRP penalty coefficients) = l_max = max_{i,j} l_{i,j}
    Set to the maximum inter-site distance for all VRP QUBOs. Standard choice but not derived from the problem structure.
  • µ_E, µ_F (QMKP penalty coefficients) = µ_E = N, µ_F = 100N
    Selected from preliminary trials to yield feasible solutions. No systematic justification provided.
assumptions (3)
  • domain assumption A feasible initial solution is available for LNS.
    Algorithm 1 (Sec. 3.1) requires x^(0) ∈ F. The paper obtains this from the naive method, but in practice a feasible initial solution may be hard to construct for some constrained problems.
  • domain assumption The Ising machine returns high-quality solutions for subproblems within a certain variable-count range.
    The central motivation (Sec. 1, Sec. 3.1) assumes that solution quality degrades when the subproblem is too large. This is empirically observed but not formally guaranteed for all Ising machine implementations.
  • domain assumption Penalty coefficients set to l_max are sufficiently large to ensure feasible minimizers.
    Sec. 4.1 states penalty coefficients are set to l_max following Ref. 6. The paper checks feasibility post-hoc and reports 100% feasible-solution rate, but the sufficiency of l_max is not proven for all instances.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size." pith.science (2026). https://pith.science/paper/LC7QOWMW

@misc{pith2026260705169,
  author       = {Pith},
  title        = {Pith review of: Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LC7QOWMW}},
  note         = {Machine review of arXiv:2607.05169}
}
read the original abstract

Ising machines are heuristic solvers for combinatorial optimization, but their solution quality can degrade when large-scale constrained problems are solved directly. Ising-machine-assisted large neighborhood search (LNS) instead repeatedly updates a feasible current solution by solving smaller subproblems. An existing feasibility-preserving method for the vehicle routing problem (VRP) re-optimizes the entire routes of selected vehicles and thus cannot adjust the subproblem size finely. We propose LNS-VT, which introduces the number of consecutive steps re-optimized per vehicle as a parameter to control the subproblem size finely while preserving feasibility. For a 300-site, 5-vehicle VRP, its best setting reduced the objective value by approximately 10\% relative to the existing method after 100 iterations, and the appropriate setting changed with the current solution quality. Applying the same principle to the quadratic multiple knapsack problem, we confirmed that an appropriate subproblem size also exists, indicating that subproblem-size control is important in Ising-machine-assisted LNS.

Figures

Figures reproduced from arXiv: 2607.05169 by the authors.

Figure 1
Figure 1. Schematics of the vehicles and sites included in the subproblems of LNS-V and LNS-VT. (a) Schematic of LNS-V, where the entire routes of the selected vehicles are re-optimized. (b) Schematic of LNS-VT, where only a contiguous part of the steps in the route of each selected vehicle is re-optimized. the subproblem size in a range where the Ising machine can obtain high-quality solutions. 3.3 Proposed subproblem genera… view at source ↗
Figure 2
Figure 2. shows the average objective values obtained by LNS-VT, LNS-V, and the naive method for the VRP with 300 non-depot sites and 5 vehicles. For LNS-VT and LNS-V, the horizontal axis represents the number of LNS iterations. For 0 10 20 30 40 50 60 70 80 90100 Number of iterations 20 25 30 35 40 45 Objective value T'=10 T'=20 T'=30 T'=40 T'=50 LNS-V naive (a) 0 10 20 30 40 50 60 70 80 90100 Number of iterations 16 17 18 1… view at source ↗
Figure 3
Figure 3. Relation between the number of non-depot site-assignment vari￾ables included in the subproblem and the objective value after 100 iterations of LNS for the VRP with 300 non-depot sites and 5 vehicles. The points represent the average values over 10 runs, and the error bars represent the standard deviations [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Number of iterations required for the average objective value to pass through each objective-value interval for LNS-V and LNS-VT with V ′ = 2. The horizontal axis represents objective-value intervals, and the ver￾tical axis represents the number of iterations required …
Figure 6
Figure 6. Figure 6: Relation between the number of iterations in LNS-VT and the num￾ber of non-depot sites whose visiting vehicle or visiting order changed. Red indicates the number of sites whose visiting vehicle changed, and blue indi￾cates the number of sites whose visiting vehicle rem…
Figure 7
Figure 7. Figure 7: Schematic of the subproblem generation method for the QMKP. In the example with K ′ = 3 and N ′ = 4, knapsacks II, III, and V and items B, E, G, and I are included in the subproblem. The other items are fixed to their assignments in the current solution. Table III. Set…
Figure 8
Figure 8. Figure 8: Relation between the number of binary variables included in the subproblem and the total profit after 100 LNS iterations for the QMKP with 200 items and 5 knapsacks. The points represent the average values over 10 runs, and the error bars represent the standard deviati…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

67 extracted references · 67 canonical work pages

  1. [1]

    To isolate the effect of subproblem generation methods in LNS, we con- sider a single-depot uncapacitated VRP, in which each vehi- cle starts from and returns to the depot

    Problem In this section, we define the VRP, the main problem treated in this study, and give its QUBO formulation. To isolate the effect of subproblem generation methods in LNS, we con- sider a single-depot uncapacitated VRP, in which each vehi- cle starts from and returns to the depot. We distinguish be- tween the objective function of the original VRP a...

    work page

  2. [2]

    Method In this section, we describe the framework of Ising- machine-assisted LNS, in which an Ising machine is used as the subproblem solver, and the subproblem generation meth- ods for the VRP. In Sec. 3.1, we describe the update procedure of LNS used in this study. In Sec. 3.2, we define the existing method LNS-V and summarize its feasibility preservati...

    work page

  3. [3]

    In the following discussion of subproblem-size scaling, we represent the subproblem size by nV var because the site-assignment variables dominate

    of free depot variables. In the following discussion of subproblem-size scaling, we represent the subproblem size by nV var because the site-assignment variables dominate. In partic- ular, when each selected vehicle visitsT−2 non-depot sites, we have|N sub|=V ′(T−2) and nV var =(V ′)2(T−2) 2.(16) Equation (16) shows that the number of site-assignment vari...

    work page

  4. [4]

    Results This section reports the numerical results for the VRP. In Sec. 4.1, we describe the settings of the numerical experi- ments. In Sec. 4.2, we compare LNS-VT with LNS-V and the naive method, and examine how the final objective value depends on the subproblem size. 4.1 Numerical Experiment Settings Table I shows the VRP instance and the parameter se...

    work page

  5. [5]

    Discussion In this section, we discuss the VRP results presented in Sec. 4. The discussion is limited to the problem instance, pa- rameter settings, and Ising-machine settings used in the nu- merical experiments. In Sec. 5.1, we examine how the appro- priate subproblem size changes during the LNS iterations. In Sec. 5.2, we discuss why different combinati...

    work page

  6. [6]

    jeu 200 75 1

    Extension to the Quadratic Multiple Knapsack Prob- lem In this section, we examine whether the design principle used in LNS-VT, namely controlling the subproblem size while preserving feasibility, can also be applied to a con- strained combinatorial optimization problem other than the VRP. As an example, we consider the QMKP. In Sec. 6.1, 10 J. Phys. Soc....

    work page

  7. [7]

    Promoting the applica- tion of advanced quantum technology platforms to social is- sues

    Conclusion In this study, we investigated Ising-machine-assisted LNS for large-scale constrained combinatorial optimization prob- lems. For the VRP, we proposed LNS-VT, a subproblem gen- eration method that introduces the number of consecutive steps re-optimized for each selected vehicle as an additional control parameter. The existing method, LNS-V , pre...

    work page

  8. [8]

    Laporte: European Journal of Operational Research59(1992) 345

    G. Laporte: European Journal of Operational Research59(1992) 345

    work page 1992

Show all 67 references
  1. [9]

    D. J. Hoitomt, P. B. Luh, and K. R. Pattipati: IEEE transactions on Robotics and Automation9(1993) 1

    1993

  2. [10]

    Chang, N

    T.-J. Chang, N. Meade, J. E. Beasley, and Y . M. Sharaiha: Computers & Operations Research27(2000) 1271

    2000

  3. [11]

    Mohseni, P

    N. Mohseni, P. L. McMahon, and T. Byrnes: Nature Reviews Physics4 (2022) 363

    2022

  4. [12]

    B. K. Chakrabarti, H. Leschke, P. Ray, T. Shirai, and S. Tanaka: Philo- sophical Transactions. Series A, Mathematical, Physical, and Engineer- ing Sciences381(2022) 20210419

    2022

  5. [13]

    Lucas: Frontiers in Physics2(2014) 74887

    A. Lucas: Frontiers in Physics2(2014) 74887

    2014

  6. [14]

    Tanaka, R

    S. Tanaka, R. Tamura, and B. K. Chakrabarti:Quantum spin glasses, annealing and computation(Cambridge University Press, 2017)

    2017

  7. [15]

    Tanahashi, S

    K. Tanahashi, S. Takayanagi, T. Motohashi, and S. Tanaka: Journal of the Physical Society of Japan88(2019) 061010

    2019

  8. [16]

    Zaman, K

    M. Zaman, K. Tanahashi, and S. Tanaka: IEEE Transactions on Com- 14 J. Phys. Soc. Jpn. FULL PAPERS puters71(2021) 838

    2021

  9. [17]

    Glover, G

    F. Glover, G. Kochenberger, R. Hennig, and Y . Du: Annals of Opera- tions Research314(2022) 141

    2022

  10. [18]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi: Science220(1983) 671

    1983

  11. [19]

    D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon: Opera- tions Research37(1989) 865

    1989

  12. [20]

    D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon: Opera- tions Research39(1991) 378

    1991

  13. [21]

    Kadowaki and H

    T. Kadowaki and H. Nishimori: Physical Review E58(1998) 5355

    1998

  14. [22]

    G. E. Santoro, R. Marton ´ak, E. Tosatti, and R. Car: Science295(2002) 2427

    2002

  15. [23]

    Hauke, H

    P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver: Reports on Progress in Physics83(2020) 054401

    2020

  16. [24]

    P. L. McMahon, A. Marandi, Y . Haribara, R. Hamerly, C. Langrock, S. Tamate, T. Inagaki, H. Takesue, S. Utsunomiya, K. Aihara, et al.: Science354(2016) 614

    2016

  17. [25]

    H. Goto, K. Tatsumura, and A. R. Dixon: Science Advances5(2019) eaav2372

    2019

  18. [26]

    H. Irie, G. Wongpaisarnsin, M. Terabe, A. Miki, and S. Taguchi: In- ternational Workshop on Quantum Technology and Optimization Prob- lems, 2019, pp. 145–156

    2019

  19. [27]

    S. Bao, M. Tawada, S. Tanaka, and N. Togawa: 2021 International Sym- posium on VLSI Design, Automation and Test (VLSI-DAT), 2021, pp. 1–4

    2021

  20. [28]

    Kanai, M

    H. Kanai, M. Yamashita, K. Tanahashi, and S. Tanaka: IEEE Access12 (2024) 157669

    2024

  21. [29]

    Kawase, S

    E. Kawase, S. Kikuchi, H. Tamai, and S. Tanaka: Scientific Reports (2026). Advance online publication, doi:10.1038/s41598-026-57443-z

    2026 doi

  22. [30]

    Zhang, G

    J. Zhang, G. L. Bianco, and J. C. Beck: Proceedings of the International Conference on Automated Planning and Scheduling, V ol. 32, 2022, pp. 404–412

    2022

  23. [31]

    Rosenberg, P

    G. Rosenberg, P. Haghnegahdar, P. Goddard, P. Carr, K. Wu, and M. L. De Prado: Proceedings of the 8th Workshop on High Performance Computational Finance, 2015, pp. 1–7

    2015

  24. [32]

    Tatsumura, R

    K. Tatsumura, R. Hidaka, J. Nakayama, T. Kashimata, and M. Ya- masaki: IEEE Access11(2023) 120023

    2023

  25. [33]

    Hidaka, Y

    R. Hidaka, Y . Hamakawa, J. Nakayama, and K. Tatsumura: IEEE Ac- cess11(2023) 142979

    2023

  26. [34]

    Takahashi, T

    K. Takahashi, T. Abe, Y . Nakamura, R. Hidaka, S. Kikuchi, and S. Tanaka: arXiv preprint arXiv:2510.23310 (2025)

    2025

  27. [35]

    Harris, Y

    R. Harris, Y . Sato, A. J. Berkley, M. Reis, F. Altomare, M. H. Amin, K. Boothby, P. Bunyk, C. Deng, C. Enderud, et al.: Science361(2018) 162

    2018

  28. [36]

    A. D. King, J. Carrasquilla, J. Raymond, I. Ozfidan, E. Andriyash, A. Berkley, M. Reis, T. Lanting, R. Harris, F. Altomare, et al.: Nature 560(2018) 456

    2018

  29. [37]

    Utimula, T

    K. Utimula, T. Ichibha, G. I. Prayogo, K. Hongo, K. Nakano, and R. Maezono: Scientific Reports11(2021) 7261

    2021

  30. [38]

    Sampei, K

    H. Sampei, K. Saegusa, K. Chishima, T. Higo, S. Tanaka, Y . Yayama, M. Nakamura, K. Kimura, and Y . Sekine: JACS Au3(2023) 991

    2023

  31. [39]

    Couzini ´e, Y

    Y . Couzini ´e, Y . Seki, Y . Nishiya, H. Nishi, T. Kosugi, S. Tanaka, and Y .-i. Matsushita: Journal of the Physical Society of Japan94(2025) 044802

    2025

  32. [40]

    Kitai, J

    K. Kitai, J. Guo, S. Ju, S. Tanaka, K. Tsuda, J. Shiomi, and R. Tamura: Physical Review Research2(2020) 013319

    2020

  33. [41]

    Tamura, Y

    R. Tamura, Y . Seki, Y . Minamoto, K. Kitai, Y . Matsuda, S. Tanaka, and K. Tsuda: Applied Physics Reviews13(2026)

    2026

  34. [42]

    Kikuchi and S

    S. Kikuchi and S. Tanaka: Scientific Reports16(2026) 20460

    2026

  35. [43]

    Venturelli, S

    D. Venturelli, S. Mandr `a, S. Knysh, B. O’Gorman, R. Biswas, and V . Smelyanskiy: Physical Review X5(2015) 031040

    2015

  36. [44]

    Kikuchi, N

    S. Kikuchi, N. Togawa, and S. Tanaka: Journal of the Physical Society of Japan92(2023) 124002

    2023

  37. [45]

    Takehara, D

    K. Takehara, D. Oku, Y . Matsuda, S. Tanaka, and N. Togawa: 2019 IEEE 9th International Conference on Consumer Electronics (ICCE- Berlin), 2019, pp. 64–69

    2019

  38. [46]

    qbsolv.https://github.com/ dwavesystems/qbsolv, 2017

    D-Wave Systems Inc. qbsolv.https://github.com/ dwavesystems/qbsolv, 2017. Accessed July 4, 2026

    2017

  39. [47]

    Okada, M

    S. Okada, M. Ohzeki, M. Terabe, and S. Taguchi: Scientific Reports9 (2019) 2098

    2019

  40. [48]

    H. Irie, H. Liang, T. Doi, S. Gongyo, and T. Hatsuda: Scientific Reports 11(2021) 8426

    2021

  41. [49]

    Hattori, H

    T. Hattori, H. Irie, T. Kadowaki, and S. Tanaka: Journal of the Physical Society of Japan94(2025) 013001

    2025

  42. [50]

    Hattori, H

    T. Hattori, H. Irie, T. Kadowaki, and S. Tanaka: Journal of the Physical Society of Japan94(2025) 074001

    2025

  43. [51]

    Chapuis, H

    G. Chapuis, H. Djidjev, G. Hahn, and G. Rizk: Proceedings of the Com- puting Frontiers Conference, 2017, pp. 63–70

    2017

  44. [52]

    Z. Peng, D. de Roux, and D. E. B. Neira: arXiv preprint arXiv:2509.11040 (2025)

    2025 arXiv

  45. [53]

    Kamishima, S

    Y . Kamishima, S. Kikuchi, and S. Tanaka: IEEE Access13(2025) 204807

    2025

  46. [54]

    Liu and I

    H. Liu and I. Sabek: arXiv preprint arXiv:2602.14263 (2026)

    2026

  47. [55]

    Karimi and G

    H. Karimi and G. Rosenberg: Quantum Information Processing16 (2017) 166

    2017

  48. [56]

    Karimi, G

    H. Karimi, G. Rosenberg, and H. G. Katzgraber: Physical Review E96 (2017) 043312

    2017

  49. [57]

    X. Liu, H. Ushijima-Mwesigwa, A. Mandal, S. Upadhyay, I. Safro, and A. Roy: arXiv preprint arXiv:1911.09810 (2019)

    1911 arXiv

  50. [58]

    Fukada, T

    K. Fukada, T. Shirai, and N. Togawa: 2024 IEEE International Confer- ence on Consumer Electronics (ICCE), 2024, pp. 1–6

    2024

  51. [59]

    S. Ide, S. Kikuchi, and S. Tanaka: arXiv preprint arXiv:2509.19280 (2025)

    2025

  52. [60]

    P. J. Eder and S. Braun: arXiv preprint arXiv:2606.01826 (2026)

    2026 arXiv

  53. [61]

    Shaw: International Conference on Principles and Practice of Con- straint Programming, 1998, pp

    P. Shaw: International Conference on Principles and Practice of Con- straint Programming, 1998, pp. 417–431

    1998

  54. [62]

    Nishimura, K

    N. Nishimura, K. Tanahashi, K. Suganuma, M. J. Miyama, and M. Ohzeki: Frontiers in Computer Science1(2019) 2

    2019

  55. [63]

    Yamashita and S

    M. Yamashita and S. Tanaka: arXiv preprint arXiv:2607.xxxxx (2026)

    2026

  56. [64]

    Chancellor: Quantum Science and Technology4(2019) 045004

    N. Chancellor: Quantum Science and Technology4(2019) 045004

    2019

  57. [65]

    Annealing Engine, 2026

    Fixstars Amplify. Annealing Engine, 2026. Accessed July 4, 2026

    2026

  58. [66]

    E. Soutif. Instances of the 0-1 Quadratic Knapsack Problem (QKP). https://cedric.cnam.fr/˜soutif/QKP/, April 2005

    2005

  59. [67]

    Hiley and B

    A. Hiley and B. A. Julstrom: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, 2006, pp. 547–552. 15

    2006

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.