{"id":"ba5fcdb5-9303-4a2e-bb2c-72373a94cd88","arxiv_id":"2508.08702","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A lattice enumeration solver solved QOBLIB market split instances up to m=14 on one CPU, extending the reported record from m=11.","lead":"This paper reports that a lattice enumeration solver, solvediophant, finds solutions to QOBLIB market split benchmark instances up to m=14 on a single CPU, extending the reported record from m=11. A generalist might read it to see how lattice reduction methods can outperform standard integer programming solvers on this NP-hard benchmark.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The abstract's 'up to m=14' is unsupported for D=100 and D=200; only the D=50 class reaches m=14.","rationale":"The reader's verdict is CONDITIONAL, which matches my assessment: the paper presents a credible but overbroad claim. The reader's weakest_assumption focuses on the lattice-reduction separation (N sufficiently large and Theorem 1 from [14]), which is a legitimate correctness concern but is not the most immediate problem for the central claim. The most load-bearing issue is that the abstract's 'up to m=14' is not supported by the table for the full QOBLIB grid, since only the D=50 variant reaches m=14. The reader did note this in the rationale ('the abstract's up to m=14 conceals that D=100 and D=200 instances are unsolved from m=10 onward'), so there is partial agreement. My proposed concrete test—checking feasibility of the m=14 D=50 solutions and rerunning the missing D classes under a fixed time budget—would determine whether the overclaim is merely a wording issue or reflects an actual limitation of the solver. Since the reader already recommended qualification and the verdict is CONDITIONAL, no change to the verdict is needed.","tokens_in":5443,"tokens_out":7491,"duration_ms":80600,"concrete_test":"Verify the reported (14,130,50) first solutions by substituting each returned x into Ax=d and checking 0≤x≤1, then rerun solvediophant on the four QOBLIB instances of (14,130,100) and (14,130,200) with the same parameter settings and a fixed wall-clock budget of, say, seven days. If any of the D=100 or D=200 instances completes, the unqualified 'up to m=14' claim could be restored; if all time out, the abstract must be amended to state the actual per-D limits: m=14 for D=50, m=10 for D=100, and m=9 for D=200.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Table 1 is the entire evidence for the headline claim. For m=14 it lists only the class (14,130,50) with a first-solution time of 140,823 seconds; the classes (14,130,100) and (14,130,200) are marked '–', meaning the exhaustive enumeration could not be completed in several days. For D=100 the largest solved class is (10,90,100), and for D=200 it is (9,80,200). Thus the abstract sentence 'instances of the QOBLIB market split benchmark problems can be solved up to m=14' does not describe the table. It describes only the D=50 sub-benchmark. If the intended reading is 'there exists some QOBLIB class at each m≤14 that is solved,' the claim is true but much weaker than the abstract suggests. If the intended reading is 'all QOBLIB market split instances up to m=14,' the claim is false. The load-bearing issue is not the lattice-reduction correctness, which is inherited from [14], but the scope of the empirical claim: the headline result is a D=50-only improvement, and the abstract obscures that.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This note reports an experimental evaluation of the author's lattice-enumeration solver solvediophant on the QOBLIB market split benchmark. The algorithm reduces the feasibility problem Ax=d with lower and upper bounds to lattice basis reduction followed by exhaustive enumeration of bounded kernel combinations, using a theorem from the author's earlier paper [14]. The central empirical claim is that QOBLIB market split instances can be solved up to m=14 on a standard computer, and Table 1 gives first-solution and all-solutions timings for classes (m, 10(m-1), D) with D in {50, 100, 200}, comparing against the GPU Schroeppel-Shamir implementation of Kempke and Koch [8].","tokens_in":5634,"tokens_out":6606,"duration_ms":66477,"significance":"If the reported timings are correct, the result is a clear empirical advance: it extends the largest solved QOBLIB market-split class from m=11 (GPU Schroeppel-Shamir, [8]) to m=14 for D=50, on a single six-year-old CPU core. The comparison against an external GPU implementation is useful, and the per-instance solution counts provide some internal consistency check. The result is, however, narrower than the abstract states, and the manuscript does not provide enough implementation detail to audit or reproduce the runtimes.","major_comments":[{"comment":"The headline claim that 'instances of the QOBLIB market split benchmark problems can be solved up to m=14' is not supported for the full QOBLIB benchmark. Table 1 shows first-solution times for m=12, 13, 14 only in the D=50 family; for D=100 the largest class with a first solution is (10,90,100) and for D=200 it is (9,80,200). The abstract should be qualified to state that the m=14 result holds for D=50 only, with the corresponding limits m=10 for D=100 and m=9 for D=200. As written, the abstract implies a uniform capability that the data actually contradict.","section":"Abstract and Section 3, Table 1"},{"comment":"The algorithm description leaves the crucial parameter N unspecified. The correctness of Step 1 depends on N being 'sufficiently large' so that lattice reduction separates kernel and non-kernel vectors, but the note gives no value or rule for choosing N and no parameters for the LLL/BKZ reduction. Consequently, the experiments are not reproducible and the reported runtimes cannot be independently checked. Please state the exact construction, including N, the reduction algorithm and its parameters, and any floating-point safeguards such as the one attributed to [10].","section":"Section 2, matrix (2)"},{"comment":"No independent verification of the enumerated solutions is reported. The table lists solution counts and timings, but there is no statement that each reported solution was checked against Ax=d or that the code contains an assertion to that effect. Since a single implementation bug in the enumeration or lattice basis recovery would invalidate the claimed 'solved' status, a short verification note, such as a residual check for all found solutions, should be added.","section":"Section 3, Table 1"}],"minor_comments":[{"comment":"The legend says that an entry of 0.00 means the average time is below 0.5 seconds, but the [8] column also contains 0.00 entries; please state whether the same rounding convention applies to the GPU times taken from [8].","section":"Section 3, Table 1"},{"comment":"The table caption does not explain why 'Number of solutions' is a list of four values for early rows and is empty for later rows; add a footnote saying that the values are ordered by file name and are omitted when exhaustive enumeration did not finish.","section":"Section 3, Table 1"},{"comment":"The sentence 'The author's most recent implementation solvediophant applied to the QOBLIB market split instances can solve instances up to m=14' is grammatically awkward and should be rephrased.","section":"Section 1"},{"comment":"The notation w_0 is used in the theorem statement but is not defined in this note; please define it as the first coordinate of w, corresponding to the x_{n+1} variable.","section":"Section 2, Theorem 1"},{"comment":"The text 'A VX2 SIMD instruction set' should read 'AVX2'.","section":"Section 3"}],"recommendation":"major_revision","confidential_remarks":"For the editor: this is a very short computational note whose main asset is the empirical benchmark. The most serious issue is the abstract overclaim for D=100 and D=200, which is easily fixable. I would also make disclosure of the parameter N and of a solution-verification step a hard condition for publication, unless the journal's policy for computational notes explicitly waives reproducibility requirements."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the D=50 result is real, the abstract oversells it.\n\nThe paper's actual contribution is a benchmark data point. The author applies his existing lattice enumeration solver to the 2025 QOBLIB market split instances and shows that for D=50, first solutions are found for all classes up to m=14, with the largest class (14,130,50) taking about 140k seconds on one six-year-old CPU. That genuinely extends the previous best of m=11 from the GPU Schroeppel-Shamir implementation. The table is honest about what was and wasn't run, and the comparison with [8] is useful.\n\nThe main soft spot is the abstract. 'Instances of the QOBLIB market split benchmark problems can be solved up to m=14' is true only for the D=50 sub-benchmark. For D=100 the largest solved class is m=10, and for D=200 it's m=9. If someone reads the abstract as a blanket statement, they'll take away something the paper doesn't show. The author should qualify it as D=50.\n\nThe second issue is reproducibility. Table 1 reports runtimes and solution counts, but no code, no parameter settings (the constant N is not given), and the algorithm description is informal with a pointer to earlier papers. That's acceptable for a short note, but it means the m=14 result can't be independently checked without chasing down [14] and reconstructing the program. A tarball or a few parameters would fix this.\n\nMinor points: the 'All' column is incomplete for larger classes, and for QOBLIB the benchmark counts as solved with one solution, which the paper does say, but it's worth remembering that the exhaustive enumeration wasn't completed for many classes. Also, the solutions aren't independently verified, though the author's earlier Theorem 1 gives a correctness argument.\n\nOverall: this is a legitimate incremental result in an established program, not a fundamental advance. It deserves a serious referee: the empirical claim is concrete and the benchmark comparison is fair. My advice would be to send it out with a request to fix the abstract and include implementation details or code.","headline":"Honest D=50 benchmark gain from m=11 to m=14; the abstract's 'up to m=14' overstates scope, but the empirical claim is real.","tokens_in":6159,"tokens_out":2096,"would_cite":false,"duration_ms":21066,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C10","11H06"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper reports that lattice reduction and enumeration solve QOBLIB market split benchmark instances up to m=14 on a standard desktop CPU, beyond the m=11 of GPU meet-in-the-middle and the m=7 of ILP solvers.","keywords":["market split problem","lattice basis reduction","integer linear feasibility","QOBLIB benchmark","bounded enumeration","0-1 integer programming","diophantine equations","meet-in-the-middle algorithm"],"falsifier":"Pick one QOBLIB class with a reported exact solution count, such as (8,70,50), and independently verify the claimed 1,265 solutions for its first instance by brute-force enumeration; any mismatch would show the enumeration step is incomplete. For the headline m=14 claim, rerun solvediophant on the four (14,130,50) instances on a different standard desktop CPU and check that a first solution is found within a few days; if it is not, the reported record does not transfer beyond the author's machine.","tokens_in":5222,"feed_emoji":"🧮","tokens_out":12598,"duration_ms":117919,"temperature":0.7,"pith_summary":"The paper reports a practical advance on the market split problem, a 0-1 linear feasibility benchmark with randomly generated coefficients introduced in 1998. The author's solver, solvediophant, converts the problem into a lattice enumeration and, running on a single six-year-old desktop CPU, finds a feasible solution for QOBLIB benchmark instances up to m=14; the largest reported case, (14,130,50), takes roughly 39 hours for a first solution. This compares with m=11 for a 2025 GPU meet-in-the-middle implementation and with about m=7 for conventional integer programming software. The paper is trying to establish that lattice basis reduction with bounded enumeration is the currently most effective method for this family of dense random 0-1 feasibility problems.","feed_headline":"Lattice enumeration solves market split to m=14 on one CPU","feed_subtitle":"Beats the GPU meet-in-the-middle record (m=11) and ILP solvers (m=7) on six-year-old hardware.","key_machinery":"The load-bearing construction is the lattice spanned by the columns of the $(m+n+1)\\times(n+1)$ matrix (2), whose first $m$ rows contain the scaled system $-N\\cdot d$ and $N\\cdot A$, and whose remaining rows encode the variable bounds through $r_{\\max}$ and $c_i$. After LLL or block Korkine-Zolotarev basis reduction with a sufficiently large constant $N$, the basis splits into vectors lying in the kernel of $Ax - d\\,x_{n+1} = 0$ and vectors that are discarded. Theorem 1 (from [14]) then states that an integer combination $w = u_0 b^{(0)} + \\cdots + u_{n-m} b^{(n-m)}$ with $w_0 = r_{\\max}$ solves the bounded system exactly when $-r_{\\max} \\le w_i \\le r_{\\max}$ for $1\\le i\\le n$. The solver exhaustively enumerates these bounded combinations, using Hölder's inequality to prune the search and limited discrepancy search to find a first solution quickly.","core_discovery":"The central claim is empirical: across the QOBLIB market split classes, the program solvediophant found a first feasible solution for every reported class with m up to 14, and exhaustively enumerated all feasible solutions for classes up to m=9, reporting exact counts such as 4,497 solutions for (9,80,50). For the largest solved class, (14,130,50), the first solution appeared after an average of about 140,823 seconds across the four instances, and for the (15,140,50) class the computation did not finish within several days. For m=10 and beyond, total enumeration was likewise not completed, so the benchmark record is for finding one solution, not for proving completeness. The paper interprets these data as evidence that lattice-based enumeration is a good candidate for the market split problem, in contrast to branch-and-cut integer programming.","pith_inferences":["The obvious next experiment is to push the m=15 class with D=50, which the paper leaves open; distributing the search tree across nodes or shuffling the input basis, as the paper suggests, may close the gap and complete the full QOBLIB range.","The paper only demonstrates feasibility finding; the real worst-case cost of the method, proving an instance infeasible, is untested at these sizes, so the method's general usefulness for arbitrary 0-1 systems remains an open question.","If the kernel-splitting step really does produce a compact basis for these dense random instances, the same lattice-plus-enumeration pattern could be turned on other bounded-variable diophantine problems, such as subset sum with intervals or design-theoretic search problems, where the runtime would again depend mainly on the enumeration pruning."],"forward_implications":["The practical ceiling for QOBLIB market split instances moves from m=11 (GPU meet-in-the-middle) to m=14 on an ordinary CPU, making the benchmark substantially more tractable and redefining the comparison point for classical and quantum solvers.","Because the QOBLIB instances are guaranteed feasible, the solver can stop at the first solution; the paper's runtimes therefore do not apply to infeasible instances, which would force a complete traversal of the search tree.","The exact solution counts reported up to m=9 provide calibration data on how the number of feasible solutions grows with m and D, which is useful for tuning other solvers.","The algorithm solves a more general bounded linear system ($Ax = d$ with $l \\le x \\le r$), so the same code applies to other 0-1 and bounded integer problems, not only the market split benchmark."],"supporting_citations":[{"why":"Defines the market split problem and the parameterized instances that the benchmark is based on.","marker":"[5]"},{"why":"Supplies the lattice reduction result guaranteeing that, for a sufficiently large N, the reduced basis separates kernel vectors from the rest, which underpins the correctness of the reduction step.","marker":"[2]"},{"why":"Proves Theorem 1, characterizing all solutions as bounded coefficient combinations of the kernel basis, and reports the earlier solver reaching m=10.","marker":"[14]"},{"why":"The 2025 GPU meet-in-the-middle implementation whose m=11 results are the baseline the paper claims to beat.","marker":"[8]"},{"why":"The benchmark library that supplies the feasible instances tested in the paper.","marker":"[9]"},{"why":"Introduces the Hölder-inequality based pruning used in the enumeration step of the algorithm.","marker":"[11]"},{"why":"Describes limited discrepancy search as an alternative enumeration strategy used to find a first solution quickly.","marker":"[15]"},{"why":"Provides the accurate dot-product summation that improves the numerical stability of the lattice basis reduction.","marker":"[10]"}],"fun_headline_variants":["Lattice trick cracks market split up to m=14","New algorithm beats GPU record for market split","CPU-only lattice method tops m=14 market split","solvediophant: lattice enumeration conquers m=14","Market split solved to m=14 with lattice search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that for a sufficiently large constant $N$, lattice reduction of matrix (2) reliably separates the basis into kernel vectors and non-kernel vectors, and that Theorem 1's bounded-coefficient characterization then captures exactly all solutions; if $N$ is too small or the reduction behaves unexpectedly, the enumeration could miss solutions or report spurious ones.","fun_headline_variants_meta":{"raw":{"variants":["Lattice trick cracks market split up to m=14","New algorithm beats GPU record for market split","CPU-only lattice method tops m=14 market split","solvediophant: lattice enumeration conquers m=14","Market split solved to m=14 with lattice search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000232,"raw_usage":{"total_tokens":1471,"prompt_tokens":907,"completion_tokens":564,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":486}},"tokens_in":523,"tokens_out":564,"duration_ms":5709,"temperature":1.0,"reasoning_tokens":486,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:32:21.702084+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Pick one QOBLIB class with a reported exact solution count, such as (8,70,50), and independently verify the claimed 1,265 solutions for its first instance by brute-force enumeration; any mismatch would show the enumeration step is incomplete. For the headline m=14 claim, rerun solvediophant on the four (14,130,50) instances on a different standard desktop CPU and check that a first solution is found within a few days; if it is not, the reported record does not transfer beyond the author's machine.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the lattice reduction result guaranteeing that, for a sufficiently large N, the reduced basis separates kernel vectors from the rest, which underpins the correctness of the reduction step."},{"cited_title":"GPU accelerated variant of Schroeppel-Shamir's algorithm for solving the market split problem","cited_arxiv_id":"2507.05045","evidence_quote":"The 2025 GPU meet-in-the-middle implementation whose m=11 results are the baseline the paper claims to beat."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the Hölder-inequality based pruning used in the enumeration step of the algorithm."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Describes limited discrepancy search as an alternative enumeration strategy used to find a first solution quickly."}],"review_version":2}