Pith. sign in

REVIEW 3 major objections 4 minor 30 references

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

T0 review · 3 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read For Ising-machine LNS on vehicle routing, the way subproblems are built matters as much as their size.

desk verdict Honest, well-controlled empirical study showing subproblem construction matters beyond size in Ising-machine LNS; the size-matching protocol is deterministic, but the main result rests on a single instance without error bars. read the letter →

arxiv 2607.05014 v2 pith:4THPVSSS submitted 2026-07-06 cond-mat.stat-mech cond-mat.dis-nnquant-ph

Masashi Yamashita , Shu Tanaka This is my paper
classification cond-mat.stat-mechcond-mat.dis-nnquant-ph
keywords IsingmachinelargeneighborhoodsearchQUBOvehicleroutingproblemsubproblemconstructionsequentialoptimizationpositionvariance
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

This paper tries to prove that, in Ising-machine-assisted large neighborhood search for vehicle routing, the way a subproblem is constructed matters independently of its size. Controlling for the number of binary variables, a route-based construction (LNS-K) finds shorter total distances than a QUBO-variable-based construction (LNS-Q), and its chosen customers become more spatially clustered over iterations. If correct, this means practitioners must treat subproblem construction as a design parameter, not just tune subproblem size. It also gives evidence that semantic structure from the current solution can improve sequential optimization.

What carries the argument

The comparison rests on a matched-size protocol that pairs vehicle-count K' in LNS-K with anchor-count n' in LNS-Q so both subproblems contain the same number of free binary variables. The geometric descriptor is the position variance of the selected customer set, which tracks spatial localization. The mechanism is that LNS-K inherits route structure from the current solution, whereas LNS-Q only sees QUBO constraints.

What would settle it

Record the per-iteration free-variable count B_m for LNS-Q. If, when restricting to iterations where B_m exactly equals the LNS-K subproblem size, LNS-Q's final distances match or beat LNS-K's, the central claim that construction rule matters at fixed size would be undercut. Alternatively, construct two subproblems with identical variable sets but different route semantics and test whether performance tracks semantics.

Watch

Extended reading notes

Core claim

Under matched subproblem sizes on a 400-customer VRP, LNS-K—which selects entire vehicle routes from the current solution—outperforms LNS-Q—which selects anchors among active QUBO variables and fixes their constraint-neighbors—on final total distance and on the pace of iterative improvement. The selected customer set in LNS-K becomes more spatially localized (position variance decreases) while LNS-Q's spread stays flat. The paper reads this as evidence that the number of binary variables alone does not characterize a subproblem.

Load-bearing premise

The comparison assumes the matched-size protocol actually gives both methods the same number of free binary variables in every iteration, but LNS-Q's free-variable count is stochastic because anchors can share constraints; if B_m fluctuates, the observed difference could be partly a size effect.

Editorial extensions

If this is right

  • Subproblem size tuning is necessary but not sufficient; construction rule becomes a design parameter.
  • Sequential optimization with Ising machines benefits from preserving semantic units (e.g., routes) of the original problem.
  • Geometric localization of selected variables may serve as a signal of solution organization during optimization.
  • LNS-K's advantage is most pronounced for small subproblems, suggesting that structure matters most when the subproblem is small.
  • The framework generalizes the LNS comparison beyond size to include structural and geometric descriptors.

Reading between the lines

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

  • If route-based structure is the causal driver, deliberately constructing subproblems from spatially coherent customer clusters—or from routes that are already locally organized—could further accelerate improvement.
  • The position variance could be used as a control variable in ablation studies to test whether localization is a cause or a consequence of better solutions.
  • The matched-size protocol's stochastic free-variable count in LNS-Q might obscure the comparison; conditioning on exact B_m per iteration could sharpen the result.
  • The same distinction between semantic-unit and representation-level subproblem construction may apply to other constrained combinatorial problems where natural units exist (e.g., jobs in scheduling, items in bin packing).
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper addresses the question of whether, in Ising-machine-assisted large neighborhood search (LNS) for vehicle routing problems, the subproblem construction rule matters beyond the mere number of binary variables. It defines two construction rules: LNS-K, which selects vehicles from the current route structure and includes the customers they serve, and LNS-Q, which selects active QUBO variables as anchors and fixes variables linked to those anchors through the constraint structure. The authors match the subproblem size B_m for the two rules on a 400-customer VRP instance (Fixstars Amplify AE), with 30 shared initial solutions, and report that LNS-K gives shorter final total distances and faster iterative improvement, while the position variance of its selected customer sets decreases over iterations. Small D-Wave experiments are used only to compare LNS with a naive full-QUBO submission under equal annealing-time budgets. The paper explicitly labels the geometric-localization explanation as non-causal and lists several limitations.

Significance. The central question is well posed and practically relevant: if subproblem construction rule matters even at equal subproblem size, then size-only tuning is insufficient for Ising-machine-assisted LNS. The paper gives precise definitions of both construction rules and a clean matched-size protocol. I verified the potential concern about stochastic B_m in LNS-Q: for KT=N, selecting n' anchors determines the number of free binary variables exactly as n'(N+1)+n'N-n'^2, and the table values follow; there is no per-iteration fluctuation. The experimental design, with shared initial solutions between methods, permits paired comparisons, and the authors are appropriately cautious in not claiming causality for the position-variance effect. The main weakness is that the load-bearing empirical claim—that LNS-K and LNS-Q differ at matched size—is presented without error bars, confidence intervals, or significance tests, on a single 400-customer instance.

major comments (3)
  1. [§4.3, Fig. 3(a)] The central claim that LNS-K yields shorter final distances than LNS-Q at matched subproblem size is supported only by averaged curves over 30 runs on one 400-customer instance, with no error bars, confidence intervals, or significance tests. The K'=5 panel shows the curves nearly overlapping, so without uncertainty quantification the differences could be within run-to-run variability. Because §5.1 and the Conclusion generalize this to 'the way in which the variables are grouped into a subproblem affects the optimization trajectory even when the number of binary variables is fixed,' this is a load-bearing gap. Please report per-iteration standard errors or confidence bands and paired tests over the 30 shared initial solutions, or explicitly restrict the claim to the observed averages on this instance.
  2. [§4.2, Fig. 2] The same statistical issue applies to the final-distance comparison. The statement that 'the best final distances obtained by LNS-K are shorter than those obtained by LNS-Q in the tested range of n'' is presented without any measure of dispersion or significance. Since the two methods start from identical initial solutions, paired comparisons are straightforward and should be reported; otherwise the figure does not establish that the apparent ordering is not due to the stochasticity of the Ising machine and random subproblem selection.
  3. [§5.5] The Limitations section acknowledges the single customer configuration and the absence of multiple problem instances, but it does not address the lack of statistical inference on the 30 runs, and the closing sentence 'These limitations do not change the main conclusion supported by Figs. 2 and 3' goes beyond what the presented evidence supports. The main conclusion is precisely what the missing error bars or significance tests would substantiate. I recommend adding a paired statistical analysis or a concrete statement of the effect size and its uncertainty.
minor comments (4)
  1. [Fig. 1] The horizontal axis label in panels (a)–(c) reads 'Number of bases', which appears to be a typo for 'Number of customers' or 'Number of customers N'. Please correct.
  2. [§2.1, Eq. (2)] The notation Q_{S_m,S_m} and Q_{S_m,\bar S_m} is used without an explicit definition of the submatrix indexing. Define these submatrices to make Eq. (2) self-contained.
  3. [§3.2] The annealing parameters left at Fixstars Amplify SDK defaults (chain strength, rescaling, spin-reversal transforms) are not listed. For reproducibility, please either specify the SDK versions and default values used or document that the defaults were queried and recorded.
  4. [Fig. 2] The horizontal axis is not clearly labeled as two separate scales for K' and n'. Clarify which points correspond to each method and how the matched-size pairs in Table II align with the plotted values.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the central claim is an experimentally tested comparison, the matched-size values are exact for KT=N, and the geometric interpretation is explicitly non-causal.

full rationale

The paper derives no prediction from fitted parameters and does not force its conclusion by construction. Its central claim—that subproblem construction rule affects optimization trajectory at fixed binary-variable count—rests on direct experimental comparison between LNS-K (Sec. 2.4) and LNS-Q (Sec. 2.5). The matched-size protocol in Sec. 3.4/Table II is exact for the KT=N case: the active set is a permutation matrix, so selecting n' anchors fixes n' distinct rows and n' distinct customer columns, giving |S_m^Q|=(KT-n')(N+1-n'), exactly the table entries; there is no per-iteration stochastic fluctuation in B_m. The position-variance analysis is explicitly labeled descriptive, not causal: Sec. 5.2 states 'the decrease in the position variance should be regarded as an observed geometric feature of LNS-K, not as a proven cause of its performance.' Prior works by the authors are cited only as background for Ising-machine LNS; none is used as a load-bearing uniqueness theorem or to justify the empirical difference. Thus no circular step of any enumerated kind is present. Remaining concerns about single-instance generality or absence of confidence intervals are statistical robustness questions, not circularity.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The paper's contribution is an empirical comparison; no new forces, particles, or conserved quantities are introduced. The only hand-set numerical inputs are QUBO penalties and subproblem-size controls. Its load-bearing assumptions are representativeness of single instances, exact per-iteration size matching, and feasibility of reconstruction.

free parameters (2)
  • μ_A = μ_B = max d_ij = 0.73–1.32 depending on instance
    Penalty coefficients for customer-visit and one-site-per-step constraints; chosen as the maximum distance rather than tuned, so they are hand-set inputs. The central comparison could change if penalties were tuned differently.
  • μ_C = 0
    The depot-stay constraint (8) is not penalized; the authors rely on KT=N (Fixstars instances) or on post-hoc reconstruction (D-Wave instances). This simplification is a modeling choice that affects feasibility pressure.
assumptions (4)
  • domain assumption Euclidean distances obey the triangle inequality, so moving depot visits to trailing steps cannot increase route distance (Sec. 3.2).
    Used in the reconstruction step to justify that packing depot visits to trailing steps preserves or improves total distance.
  • domain assumption A single random customer coordinate set per N is representative enough to compare construction rules; the 30 initial solutions provide the only randomness studied (Sec. 3.1, 5.5).
    The matched-size comparison is performed on one 400-customer instance, so the conclusion's generality depends on this representativeness assumption.
  • domain assumption For small N, CBC MIP solutions are exact and exhaustive enumeration confirms them (Sec. 4.1).
    The normalized-distance comparison in Fig. 1(b) relies on these exact optima.
  • domain assumption The reconstruction step maps raw Ising samples to feasible VRP solutions without systematically favoring one construction rule (Sec. 3.2).
    LNS-K and LNS-Q both feed through the same reconstruction, but a differential interaction between reconstruction and subproblem structure could confound the comparison.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search." pith.science (2026). https://pith.science/paper/4THPVSSS

@misc{pith2026260705014,
  author       = {Pith},
  title        = {Pith review of: Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4THPVSSS}},
  note         = {Machine review of arXiv:2607.05014}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2607.05014 by the authors.

Figure 1
Figure 1. (b) also shows that, among the feasible solutions obtained in the tested instances, LNS gives shorter normal￾ized total distances than the naive approach. Thus, under the same total annealing-time budget, solving smaller subprob￾lems sequentially improves the solution quality for the small instances tested on D-Wave Advantage 4.1. Figures 1(c) and 1(d) show the corresponding results ob￾tained with Fixstars Amplify A… view at source ↗
Figure 1
Figure 1. (d) shows the iterative behavior for the 400- customer instance. The total distance of the current solution decreases rapidly during the early iterations. This distance drops below the final total distance obtained by the naive ap￾proach well before the full 60-iteration budget is consumed. These results support the use of Ising-machine-assisted LNS as a sequential optimization framework. The following sections focu… view at source ↗
Figure 2
Figure 2. Final total distance obtained by LNS-K and LNS-Q for a vehicle routing problem with 400 customers. LNS-K constructs a subproblem from selected vehicles and the customers visited by those vehicles in the current solution, whereas LNS-Q constructs a subproblem from QUBO variables and the associated constraints. The horizontal labels indicate K ′ for LNS-K and n ′ for LNS-Q. The corresponding numbers of binary variable… view at source ↗
Figures from the paper (3 more)
Figure 2
Figure 2. Figure 2: Final total distance obtained by LNS-K and LNS-Q for a vehicle routing problem with 400 customers. LNS-K constructs a subproblem from selected vehicles and the customers visited by those vehicles in the current solution, whereas LNS-Q constructs a subproblem from QUBO …
Figure 3
Figure 3. Figure 3: (a), [PITH_FULL_IMAGE:figures/full_fig_p007_3.png]
Figure 3
Figure 3. Figure 3: (a), [PITH_FULL_IMAGE:figures/full_fig_p008_3.png]

Review history (2 revisions) →

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

30 extracted references · 2 linked inside Pith

  1. [1]

    Introduction Large-scale constrained combinatorial optimization prob- lems often require quadratic unconstrained binary optimiza- tion (QUBO) formulations with many binary variables. Ising machines have been developed as hardware or software solvers for finding low-energy states of Ising models or QUBO models.1–7) They provide a computational approach to ...

    arXiv 2026

  2. [2]

    Section 2.1 describes how a restricted subproblem is obtained from a QUBO by fixing a subset of binary variables

    Problem Formulation and Subproblem Construction In this section, we set up the problem and the subproblem construction rules used in the rest of the paper. Section 2.1 describes how a restricted subproblem is obtained from a QUBO by fixing a subset of binary variables. Section 2.2 for- mulates the vehicle routing problem as a QUBO, and Sec- tion 2.3 prese...

  3. [3]

    Sec- tion 3.1 specifies the VRP instances

    Numerical Setup This section describes the numerical experiments. Sec- tion 3.1 specifies the VRP instances. Section 3.2 describes the two Ising machines and the annealing conditions. Sec- tion 3.3 explains the different roles of the two machines, and Section 3.4 defines the matched-size protocol used to compare LNS-K and LNS-Q. 3.1 Problem instances We u...

  4. [4]

    Section 4.1 compares LNS with the naive approach under an equal annealing-time budget

    Results This section presents the numerical results. Section 4.1 compares LNS with the naive approach under an equal annealing-time budget. Section 4.2 examines how the final solution quality depends on the subproblem construction rule. Section 4.3 compares the iterative improvement processes at matched subproblem sizes, and Section 4.4 analyzes the geo- ...

    2000

  5. [5]

    Sec- tion 5.1 argues that the subproblem size alone is not a suf- ficient descriptor of a subproblem

    Discussion This section discusses the implications of the results. Sec- tion 5.1 argues that the subproblem size alone is not a suf- ficient descriptor of a subproblem. Section 5.2 interprets the geometric localization observed for LNS-K. Section 5.3 dis- cusses the different roles of the route structure and the QUBO structure. Section 5.4 summarizes the ...

  6. [6]

    Promoting the application of advanced quantum technology platforms to social issues

    Summary and Conclusion We investigated Ising-machine-assisted sequential opti- mization for VRPs. The focus of this study was the role of subproblem construction in LNS. We compared two construc- tion rules. LNS-K constructs a subproblem from selected ve- hicles and the customers visited by those vehicles in the cur- rent solution. LNS-Q constructs a subp...

  7. [7]

    Lucas: Frontiers in Physics2(2014) 74887

    A. Lucas: Frontiers in Physics2(2014) 74887

    2014

  8. [8]

    Kochenberger, J

    G. Kochenberger, J. K. Hao, F. Glover, M. Lewis, Z. L ¨u, H. Wang, and Y . Wang: Journal of Combinatorial Optimization28(2014) 58

    2014

Show all 30 references
  1. [9]

    Tanaka, R

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

    2017

  2. [10]

    Tanahashi, S

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

    2019

  3. [11]

    Zaman, K

    M. Zaman, K. Tanahashi, and S. Tanaka: IEEE Transactions on Com- puters71(2021) 838

    2021

  4. [12]

    Mohseni, P

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

    2022

  5. [13]

    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

  6. [14]

    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

  7. [15]

    Booth, S

    M. Booth, S. P. Reinhardt, and A. Roy: Partitioning Optimization Prob- lems for Hybrid Classical/Quantum Execution (2017)

    2017

  8. [16]

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

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

    2017

  9. [17]

    Karimi, G

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

    2017

  10. [18]

    Karimi and G

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

    2017

  11. [19]

    Okada, M

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

    2019

  12. [20]

    Nishimura, K

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

    2019

  13. [21]

    Okada, M

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

    2019

  14. [22]

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

    2021

  15. [23]

    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

  16. [24]

    Kikuchi, N

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

    2023

  17. [25]

    Noguchi, K

    T. Noguchi, K. Fukada, S. Bao, and N. Togawa: IEEE Access11(2023) 100383

    2023

  18. [26]

    Hattori, H

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

    2025

  19. [27]

    Hattori, H

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

    2025

  20. [28]

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

    2025 arXiv

  21. [29]

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

    2025

  22. [30]

    Toth and D

    P. Toth and D. Vigo:The vehicle routing problem(SIAM, 2002). 11

    2002

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.