{"id":"235c0aef-2c1a-479c-8731-cc55cd580048","arxiv_id":"2501.05624","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A CQM-based quantum annealing formulation solves small shipment rerouting instances with the same optimal cost as an exact MIP solver, but the speed comparison rests on very small, non-binding test cases.","lead":"This paper formulates a shipment rerouting problem as mixed-integer programs and as constrained quadratic models for D-Wave's hybrid quantum-classical solver. Experiments on tiny instances up to 5 shipments compare CPLEX against the quantum hybrid solver and report matching solution quality with lower solver time for larger shipment counts.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The classical MIP objective C9 mis-linearizes the stop-to-stop indicator as (X+X'-1)/2, so the reported 'optimal' classical baselines do not minimize the stated SRP cost; QA's match with these baselines is therefore not evidence of optimality.","rationale":"The paper's central claim is that quantum annealing matches the classical exact solution while running much faster. The classical exact solution is defined by the MIP in Section 2, and its objective C9 is internally inconsistent: the expression (X+X'-1)/2 is not equivalent to the product indicator X*X' for 0-1 variables, and it assigns negative costs to unused stops and unused trucks. This invalidates the classical formulation as an exact solver for SRP and makes the equality in Table 8 untrustworthy. The QA formulation D9 is correct on its face, but without a correct baseline the empirical comparison cannot establish optimality or speed advantage for meaningful SRP instances. I agree with the reader's rejection, and I note the reader also identified the C9 error in the rationale, though the reader's weakest_assumption emphasized instance triviality rather than this algebraic flaw; hence partial agreement. A direct recomputation with the corrected objective is a straightforward, decisive check.","tokens_in":12204,"tokens_out":6549,"duration_ms":67989,"concrete_test":"Implement C9 exactly as written in the paper for the Sioux Falls m=2 instance and evaluate the objective for a feasible solution in which one of the two trucks is unused: that unused truck contributes a strictly negative w_{j,q} for every q, proving the objective is not the true travel cost. Then reformulate the classical MIP with the correct product-form objective D9, solve with CPLEX, and compare the resulting optimal cost to the reported 30.0 in Table 8; a mismatch confirms that the classical baseline is miscalibrated and the QA-superiority claim lacks a valid comparison.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2's objective C9 defines w_{j,q} using terms like d(p(s_i,s_i')) * (X(i,j,q-1) + X(i',j,q) - 1)/2. For binary variables this yields -0.5 when both variables are 0, 0 when exactly one is 1, and +0.5 only when both are 1. It is not the product X*X' that the preceding if-case requires. Consequently, empty or unused trucks contribute large negative costs, so the MIP minimizes a spurious objective rather than the actual sum of rental fees plus C times route distance. The 'optimal' costs in Table 8, and the claimed equality between the classical SRP and quantum QA solutions, rest on this invalid baseline. QA's D9 correctly uses products, so the reported equality likely reflects the trivial decomposition of the test instances (m small, loads 50, capacity 100, rental 1) rather than a true matching of optima. The central claim that the quantum annealing solver works optimally and faster is not supported because the classical yardstick is mathematically mis-specified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a shipment rerouting problem (SRP) that combines sequencing and packing decisions for capacitated trucks on a hub network. It proposes two classical mixed-integer programming formulations (with and without a dispatch center) and two constrained-quadratic-model (CQM) formulations intended for D-Wave quantum annealing. The experiments compare CPLEX and the D-Wave LeapHybridCQMSampler on six public transportation networks with one to five shipments, and the paper claims that the quantum annealing solver produces optimal or near-optimal solutions much faster than the classical solver.","tokens_in":12345,"tokens_out":9771,"duration_ms":96341,"significance":"If its claims were correct, the paper would offer a useful quantum-annealing encoding for a logistics problem with both packing and sequencing constraints, and it would present an empirical speed comparison on standard benchmark networks. Credit is due for formulating the CQM model with a correct bilinear route-cost objective (D9), for using public transportation networks, and for reporting preprocessing times. However, the main classical baseline is invalidated by a mathematical error in objective C9, and the experimental instances do not exercise the capacity constraints that make SRP hard. As a result, the central claims that the classical formulations are exact and that the quantum annealing solver matches them optimally and runs faster are not supported by the presented evidence.","major_comments":[{"comment":"The linearized objective is mathematically wrong. For binary variables, (X(i,j,q-1) + X(i',j,q) - 1)/2 evaluates to -0.5 when both variables are 0, to 0 when exactly one is 1, and to +0.5 only when both are 1. It is not the product X*X' that the preceding if-case requires. Consequently, unused stop pairs contribute large negative terms to w_{j,q}, and the MIP minimizes a spurious objective rather than the sum of rental fees plus C times the actual route distance. The same error appears in the dispatch-center term c_beta, which uses (Y(i,j,q) - sum_{i'} [X(i',j,q+1)+Y(i',j,q+1)])/2 instead of the product form used in D9. Therefore the CPLEX \"optimal\" costs in Table 8 are not minimizers of the stated SRP cost, and the claim in Section 4.2.4 that the quantum annealing algorithms work optimally as the classical solutions is not supported. The quantum objective D9 correctly uses products, so the classical and quantum formulations are not equivalent as claimed; a correct classical encoding would require either quadratic terms or auxiliary variables with McCormick-type linearization.","section":"Section 2, objective C9 and the dispatch-center c_beta term"},{"comment":"The experimental design does not exercise the packing-sequencing interaction that makes SRP hard. With m = 1..5 shipments, uniform load 50, truck capacity 100, K = m trucks, and rental fee 1, every instance can be solved by assigning each shipment to its own dedicated truck, and the capacity constraint is never binding (no truck is ever forced to carry two shipments). The matching costs in Table 8 (SRP and QA equal, SRP-D and QA-D equal) are therefore consistent with the trivial decomposition of the instances and do not demonstrate that the quantum solver finds optimal solutions for capacitated SRP. The claim that the solver \"generates near-optimal or optimal solutions\" requires experiments in which the capacity constraint is active and in which the optimal solution must pack multiple shipments onto a truck; no such instances are reported.","section":"Section 4.1 and Section 4.2.4"},{"comment":"The runtime comparison is not apples-to-apples. CPLEX times are local solver times on a specified CPU, whereas the D-Wave times are LeapHybridCQMSampler API times, which include submission, queueing, and hybrid classical-quantum post-processing. The paper acknowledges that wall-clock time is not used but does not establish that the two metrics measure the same quantity. In addition, Tables 4 and 5 do not state whether the reported numbers are averages over the five runs and over the six networks, or whether they are representative single runs. The near-constant QA times (about 3.0-3.2 seconds for all m) are consistent with fixed API overhead rather than a scaling advantage, and the claim that QA times grow linearly while CPLEX times grow exponentially is based on only five values of m and no larger instances. The speed advantage asserted in the abstract and Section 4.2.2 is therefore not established.","section":"Section 4.2.2, Tables 4 and 5, and Figure 1"}],"minor_comments":[{"comment":"The reductions to TSP and partition are sketched informally. In the TSP reduction, the condition that the minimum rental cost exceeds the total cost of all hub-to-hub paths is not clearly stated: the rental cost is still paid for the single truck, so the reasoning that the optimum minimizes distance only should be spelled out. The partition reduction shows a feasibility argument for a special case; it would be cleaner to state explicitly that the decision version of SRP is NP-complete.","section":"Section 1, NP-hardness reductions"},{"comment":"After listing constraints C1-C9, the paper gives a formula for the total number of conditions as \"4m2K + 2m + K·2m + m·K + m·K·2m + 2m·K + 2m·K + 2m·K + 2m·K\". This expression is not derived from the listed constraints and appears to overcount or misidentify the constraint types; the paper should present a verifiable count for each constraint family.","section":"Section 2, condition count"},{"comment":"The statement that the quantum formulations use \"about 1/6 of\" the classical variables is only approximately true for m=5 (505 vs. 5005 for SRP, 730 vs. 5230 for SRP-D); for m=1 the ratio is closer to 1/2. The claim should be qualified by the size of m.","section":"Section 4.2.3, variable counts"},{"comment":"The quality comparison is reported only for Sioux Falls, yet the concluding sentence in Section 4.2.4 generalizes to all tested networks. If the other networks were also tested, the corresponding costs should be reported or summarized; otherwise the optimality claim is based on a single network.","section":"Section 4.2.4, Table 8"},{"comment":"There are frequent typographical and grammar issues, such as missing articles and awkward phrasing (e.g., \"we count the cost w_{j,q} that the truck j's traveling distance\"). A careful proofread is needed before resubmission.","section":"General presentation"}],"recommendation":"reject","confidential_remarks":"The mathematical error in objective C9 is elementary and central: the classical MIP is not an exact formulation of the stated cost, so the CPLEX optimal solutions are not valid baselines. Combined with the trivial experimental instances and the inconsistent runtime metrics, the paper's main claims are unsupported. The error is fixable in principle, but the revision would require correcting the objective, re-running all experiments on instances that actually stress the capacity constraints, and redoing the runtime comparison with comparable metrics. Given the scope of these changes, a fresh submission rather than a minor revision seems more appropriate. The reader's stress-test concern about the unused capacity constraint lands fully on reading the manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the CQM formulations for the multi-truck shipment rerouting problem with capacities and a dispatch center are real work and a legitimate extension of the single-route QUBO and SSRP results they cite. Second, the central empirical claim—that quantum annealing matches the classical optimum and runs faster—rests on a classical baseline that is mis-specified. The C9 objective uses (X+X'-1)/2 to linearize the product X*X', which is wrong for binary variables: it gives -0.5 when both are 0, so unused trucks accumulate negative cost. The quantum D9 uses the correct product. The reported equality between QA and CPLEX therefore only shows that QA matches a solver that is minimizing the wrong objective on tiny instances.\n\nWhat the paper does well: the constraint lists C1-C8 and D1-D8 are clearly laid out, the capacity constraints and the dispatch-center extension are sensible, and the NP-hardness reductions are standard but correct. The preprocessing on real transportation networks is a nice touch, and they are honest that the CQM variable count is much lower than the MIP count. There is no circular reasoning; the QA results are benchmarked against an independent solver, which is the right instinct.\n\nThe soft spots are not minor. Beyond the C9 error, the runtime comparison mixes local CPLEX solver time with D-Wave API-reported hybrid solver time, which is apples-to-oranges. The test instances are up to only 5 shipments, with loads of 50, capacity 100, and rental cost 1, so the capacity constraint never binds and the hard packing-sequencing interaction is never exercised. Quality results are reported for only one network and without error bars. The conclusion that QA is 'much faster' is not supported by this experimental design.\n\nThis paper is for readers interested in quantum annealing formulations for logistics, but as it stands it is not ready for referees. The fix is straightforward: correct the C9 linearization, rerun on instances where capacity actually binds, and make the runtime comparison apples-to-apples. I would not cite it in its current form, and I would not send it to peer review yet. Desk reject with encouragement to revise is the right call.","headline":"The CQM formulations are a genuine extension, but a mis-linearized classical objective C9 invalidates the 'QA matches optimal' comparison, so the paper's central empirical claim does not survive.","tokens_in":12902,"tokens_out":1804,"would_cite":false,"duration_ms":19046,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper argues that a constrained-quadratic-model quantum annealing formulation solves small shipment rerouting problems to optimality in roughly constant time, where an exact classical MILP solver's runtime grows steeply with shipment…","keywords":["shipment rerouting problem","quantum annealing","constrained quadratic model","mixed-integer linear programming","capacitated truck routing","NP-hard optimization","hybrid quantum-classical solver","logistics optimization"],"falsifier":"On Sioux Falls, run the same comparison with six shipments and only three trucks of capacity 100, so every truck must be full; if the quantum solver's runtime stops being flat or its total cost exceeds the classical optimum, the paper's optimality-and-constant-time claim fails on that class of instances.","tokens_in":11957,"feed_emoji":"🚚","tokens_out":8972,"duration_ms":86514,"temperature":0.7,"pith_summary":"This paper studies the shipment rerouting problem (SRP), an NP-hard logistics problem in which a fleet of capacitated trucks with rental costs must carry indivisible goods from source hubs to destination hubs at minimum rental-plus-travel cost. The authors build two exact mixed-integer linear programs for SRP—one plain and one with a dispatch center—and translate both into constrained-quadratic-model (CQM) formulations suitable for quantum annealing. They test all four formulations on six road networks with 1 to 5 shipments and report that the quantum annealing solvers return the same total costs as the classical solver while their measured runtimes stay near 3 seconds, against classical runtimes that climb from 0.03 to over 100 seconds. If these results hold beyond the tested instances, hybrid quantum-classical solvers would offer a practical way to solve small SRP instances to optimality faster than exact classical branch-and-cut.","feed_headline":"Quantum annealing matches exact solvers on small shipment rerouting","feed_subtitle":"On 1–5 shipment tests, quantum runtime stays near 3 seconds while classical solver time climbs steeply.","key_machinery":"The load-bearing object is the constrained-quadratic-model reformulation of the stop-based MILP. Both formulations use binary variables $X(i,j,p)$ and $Y(i,j,p)$ marking whether shipment $i$'s source or destination is the $p$-th stop of truck $j$, plus $Z(j)$ for truck use; the CQM version writes the transition cost between consecutive stops directly as quadratic products such as $X(i,j,q-1)X(i',j,q)$, and hands the constraints D1–D8 to a hybrid quantum-classical CQM solver. This avoids the auxiliary $w_{j,q}$ variables of the MILP's objective C9 and reduces the variable count from $O(m^2K)$ with a large constant to $O(m^2K)$ with a much smaller constant—exactly the comparison the experiments display. The dispatch-center variant adds $c_\\alpha$ and $c_\\beta$ terms that anchor each route to a central depot and, on the classical side, prune the search space.","core_discovery":"The paper's central claim is that a CQM-based quantum annealing formulation can solve the shipment rerouting problem optimally—at least on all tested instances—and does so in roughly constant wall-clock time, whereas classical MILP solve time grows quickly with the number of shipments. In the experiments, both quantum formulations match the classical optimum on Sioux Falls, and the authors write that the quantum annealing algorithms work optimally as the classical solutions. The reason offered is structural: the quantum CQM formulation expresses route-transition costs directly as quadratic products of binary stop variables, eliminating the auxiliary linearization variables of the MILP, so the binary-variable count is about one sixth of the MILP count. The authors conclude by recommending the quantum annealing algorithms for SRP on the strength of this speed at equal solution quality.","pith_inferences":["The roughly three-second floor on quantum runtimes is likely dominated by fixed hybrid-solver submission and communication overhead; if that overhead fell, the crossover point at which quantum solves beat the classical solver would move to even smaller instances.","A natural next experiment, not run in the paper, is to make the capacity constraint bind—for example, six 50-unit shipments with only three 100-unit trucks, so every truck must be full—and then compare the two approaches; that would test whether the joint packing-sequencing formulation remains optimal when packing actually constrains routes.","Because the CQM model optimizes all trucks jointly in one quadratic program, unlike the earlier single-route QUBO heuristic cited in the paper, the same modeling move may transfer to other combined assignment-and-routing logistics problems with indivisible loads.","The paper's claim is about small instances; if the flat quantum runtime persists to larger m (6–10 shipments), the practical use case would be real-time rerouting decisions where an exact classical solver would time out."],"forward_implications":["On all tested instances, the two quantum annealing formulations return the same total cost as the classical MILP formulations, so the paper claims they are optimal for those instances.","The measured runtime of the quantum solver stays near 3 seconds as the number of shipments grows from 1 to 5, while the classical solver's runtime grows from 0.03 to 101.3 seconds without a depot and from 0.02 to 11.9 seconds with a depot.","The CQM formulations use roughly one sixth as many binary variables as the MILP formulations (505 vs. 5005 at five shipments), which the paper identifies as the structural source of the speed difference.","Adding a dispatch center to the classical formulation sharply reduces its solve time, indicating that constraints anchoring routes to a depot prune the classical search space.","The paper recommends using the quantum annealing algorithms for the shipment rerouting problem, based on their speed at matching the classical optimum."],"supporting_citations":[{"why":"Prior single-route QUBO formulation whose iterative route-selection heuristic the new CQM formulation replaces with a joint multi-truck optimization.","marker":"[8]"},{"why":"QUBO formulation of the segmented shipment rerouting variant whose potentially exponentially many candidate-path variables motivate the stop-based CQM variables.","marker":"[14]"},{"why":"Source of the six road-network instances used for all experiments.","marker":"[10]"},{"why":"Library used to build the CQM models that are submitted to the hybrid quantum-classical solver.","marker":"[15]"},{"why":"Background on Ising-machine software that the CQM/QUBO toolchain builds on.","marker":"[11]"},{"why":"Standard mapping of NP problems to Ising and QUBO form that underlies quantum annealing formulations.","marker":"[6]"}],"fun_headline_variants":["Quantum annealing matches optimal routes, then outruns MILP","Quantum annealing: flat runtime while classical solver soars","Quantum annealing solves shipment rerouting optimally, faster","Quantum annealing beats classical on shipment rerouting scaling","Quantum annealing keeps rerouting time flat as MILP climbs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central empirical conclusion assumes that instances with 1–5 shipments, all loads 50, all truck capacities 100, and all rental fees 1 are representative enough of SRP's difficulty; because the capacity limit is never varied or pushed to its binding point, the packing–sequencing interaction that makes the problem hard is not exercised.","fun_headline_variants_meta":{"raw":{"variants":["Quantum annealing matches optimal routes, then outruns MILP","Quantum annealing: flat runtime while classical solver soars","Quantum annealing solves shipment rerouting optimally, faster","Quantum annealing beats classical on shipment rerouting scaling","Quantum annealing keeps rerouting time flat as MILP climbs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000242,"raw_usage":{"total_tokens":1488,"prompt_tokens":872,"completion_tokens":616,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":488,"completion_tokens_details":{"reasoning_tokens":539}},"tokens_in":488,"tokens_out":616,"duration_ms":7080,"temperature":1.0,"reasoning_tokens":539,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:12:51.254498+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On Sioux Falls, run the same comparison with six shipments and only three trucks of capacity 100, so every truck must be full; if the quantum solver's runtime stops being flat or its total cost exceeds the classical optimum, the paper's optimality-and-constant-time claim fails on that class of instances.","supporting_citations":[{"cited_title":"Solving a real-world package delivery routing problem using quantum annealers","cited_arxiv_id":null,"evidence_quote":"Prior single-route QUBO formulation whose iterative route-selection heuristic the new CQM formulation replaces with a joint multi-truck optimization."},{"cited_title":"Solving the shipment rerouting problem with quantum optimization techniques","cited_arxiv_id":null,"evidence_quote":"QUBO formulation of the segmented shipment rerouting variant whose potentially exponentially many candidate-path variables motivate the stop-based CQM variables."},{"cited_title":"Transportation networks for research","cited_arxiv_id":null,"evidence_quote":"Source of the six road-network instances used for all experiments."},{"cited_title":"PyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form","cited_arxiv_id":"2103.01708","evidence_quote":"Library used to build the CQM models that are submitted to the hybrid quantum-classical solver."},{"cited_title":"Application of ising machines and a software development for ising machines","cited_arxiv_id":null,"evidence_quote":"Background on Ising-machine software that the CQM/QUBO toolchain builds on."},{"cited_title":"Ising formulations of many NP problems","cited_arxiv_id":null,"evidence_quote":"Standard mapping of NP problems to Ising and QUBO form that underlies quantum annealing formulations."}],"review_version":1}