Solving the Market Split Problem with Lattice Enumeration

Alfred Wassermann

REVIEW 3 major objections 5 minor 17 references

Solving the Market Split Problem with Lattice Enumeration

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2508.08702 v2 pith:VRVEL67O submitted 2025-08-12 math.OC

Alfred Wassermann This is my paper · ORCID

classification math.OC MSC 90C1011H06

keywords marketsplitproblemlatticebasisreductionintegerlinearfeasibilityQOBLIBbenchmarkboundedenumeration0-1programmingdiophantineequationsmeet-in-the-middlealgorithm

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Short version: the D=50 result is real, the abstract oversells it.

The 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.

The 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.

The 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.

Minor 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.

Overall: 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.

Referee Report

3 major / 5 minor

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].

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 (3)

[Abstract and Section 3, Table 1] 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 2, matrix (2)] 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 3, Table 1] 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.

minor comments (5)

[Section 3, Table 1] 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 3, Table 1] 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 1] 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 2, Theorem 1] 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 3] The text 'A VX2 SIMD instruction set' should read 'AVX2'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the result is an empirical benchmark claim, and the self-cited Theorem 1 is a parameter-free external theorem rather than a fitted input.

full rationale

The paper's central claim is an empirical benchmark report: the author measures first-solution and all-solution runtimes of solvediophant on QOBLIB instances and compares them with a GPU Schroeppel-Shamir implementation from [8]. No parameter is fitted to the benchmark data and then renamed as a prediction; the runtimes are direct observations. The only potentially load-bearing self-citation is Theorem 1 of [14], which characterizes the coefficient bounds for lattice enumeration. This theorem is a parameter-free mathematical characterization with stated assumptions and does not itself assert anything about the QOBLIB benchmarks; using it as a correctness basis is standard citation practice, not circularity. The algorithm additionally relies on the 'N sufficiently large' separation condition from [2], an independent source. The abstract's wording that instances 'can be solved up to m=14' is imprecise because Table 1 reaches m=14 only for the D=50 class, and for D=100 and D=200 the largest first-solution entry is m=10 and m=9, respectively; however, that is a scope-of-claim accuracy issue, not a circular derivation. No equation in the paper reduces to its own input, and no fitted parameter is presented as a prediction.

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

The experimental claim rests on prior lattice results (N sufficiently large, kernel basis separation), on Theorem 1 of [14], and on QOBLIB feasibility guarantees. No new entities are invented. N is an unspecified free parameter that could affect correctness.

free parameters (1)

N
A large integer constant used in the lattice matrix (2). The paper only states it must be 'sufficiently large' [2], but does not give its value or how it is computed for each instance. The choice affects whether the reduced basis separates as required.

assumptions (3)

standard math Theorem 1 of [14]: an integer linear combination of the kernel basis vectors with w0=rmax is a solution of (1) iff all other coordinates are within the bounds -rmax and rmax.
This theorem is the theoretical foundation of the enumeration step and is cited from the author's 2002 paper. It is not re-proven here, but it is published and peer-reviewed.
domain assumption For sufficiently large N, LLL/BKZ reduction of matrix (2) yields n-m+1 kernel vectors with zero entries in the first m rows and m vectors with at least one nonzero entry there.
The separation property is asserted with a citation to [2]. The note does not derive or verify this property for the specific instances solved.
domain assumption Every QOBLIB market split instance has at least one feasible solution.
The note relies on the QOBLIB library's statement that instances were constructed to be feasible. This matters for the claim that finding the first solution counts as solving the instance.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Solving the Market Split Problem with Lattice Enumeration." pith.science (2026). https://pith.science/paper/VRVEL67O

@misc{pith2026250808702,
  author       = {Pith},
  title        = {Pith review of: Solving the Market Split Problem with Lattice Enumeration},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VRVEL67O}},
  note         = {Machine review of arXiv:2508.08702}
}

abstract

The market split problem was proposed by Cornu\'ejols and Dawande in 1998 as benchmark problem for algorithms solving linear systems with binary variables. The recent (2025) Quantum Optimization Benchmark Library (QOBLIB) contains a set of feasible instances of the market split problem. In QOBLIB an instance of the market split problem is considered as solved as soon as at least one feasible solution has been found. The market split problem seems to be difficult to solve with the conventional branch-and-cut approach of integer linear programming software which reportedly can handle QOBLIB instances up to $m=7$. In contrast, a new GPU implementation of the Schroeppel-Shamir algorithm solves instances up to $m=11$. In this note we report about experiments with an algorithm that reduces the market split problem to a lattice problem. With the author's most recent implementation - named solvediophant - instances of the QOBLIB market split benchmark problems can be solved up to $m=14$ on a standard computer.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 11 canonical work pages

[8]

GPU accelerated variant of Schroeppel-Shamir's algorithm for solving the market split problem

Kempke, N.C., Koch, T.: GPU accelerated variant of Schroeppel-Shamir’s algorithm for solving the market split problem (2025). URL https://arxiv.org/abs/2507.05045

work page Pith review arXiv 2025
[14]

Wassermann, A.: Attacking the market split problem with lattice point enumeration. J. Combinatorial Optimization 6, 5–16 (2002). URL https://doi.org/10.1023/A: 1013355015853

doi:10.1023/a: 2002
[10]

Ogita, T., Rump, S.M., Oishi, S.: Accurate sum and dot product. SIAM J. Sci. Comput. 26(6), 1955–1988 (2005). URL https://doi.org/10.1137/030601818

doi:10.1137/030601818 2005
[1]

Aardal, K., Bixby, R.E., Hurkens, C.A.J., Lenstra, A.K., Smeltink, J.W.: Market split and basis reduction: Towards a solution of the Cornu ´ejols-Dawande instances. In: R.E. 4 Burkard, G. Cornu ´ejols, G.J. Woeginger (eds.) Integer Programming and Combinatorial Optimization, 7th International IPCO Conference, pp. 1–16. Lecture Notes in Computer Science 16...

work page 1999
[2]

Aardal, K., Hurkens, C.A.J., Lenstra, A.K.: Solving a linear diophantine equation with lower and upper bounds on the variables. In: R.E. Bixby, E.A. Boyd, R.Z. R ´ıos-Mercado (eds.) Integer Programming and Combinatorial Optimization, 6th International IPCO Con- ference, pp. 229–242. Lecture Notes in Computer Science 1412, Springer-Verlag, Heidel- berg (19...

work page doi:10.1007/3-540-69346-7_18 1998
[3]

Japan Journal of Industrial and Applied Mathematics (2025)

Aono, Y ., Nguyen, P.Q.: On tiny-probability lattice enumeration. Japan Journal of Industrial and Applied Mathematics (2025). URL https://doi.org/10.1007/ s13160-025-00713-6

work page 2025
[4]

In: Par- allel Virtual Machine – EuroPVM’96 (Munich, 1996), Lecture Notes in Comput

Betten, A., Wassermann, A.: {0,1}-solutions of integer linear equation systems. In: Par- allel Virtual Machine – EuroPVM’96 (Munich, 1996), Lecture Notes in Comput. Sci. , vol. 1156, pp. 311–314. Springer, Berlin (1995). URL https://doi.org/10.1007/ 3540617795_40

work page 1995
[5]

Cornu ´ejols, G., Dawande, M.: A class of hard small 0-1 programs. In: R.E. Bixby, E. Boyd, R. R ´ıos-Mercado (eds.) Integer Programming and Combinatorial Optimiza- tion. 6th International IPCO Conference, Houston, Texas, June 1998. Springer Lecture Notes in Computer Science 1412, pp. 284–293. Springer-Verlag, Heidelberg (1998). URL https://doi.org/10.100...

doi:10.1007/3-540-69346-7_22 1998

Show all 17 references

[6]

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman and Company (1979)

1979
[7]

In: Proceedings of the 14th International Joint Conference on Artificial Intelligence - V olume 1, IJCAI’95, pp

Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence - V olume 1, IJCAI’95, pp. 607–
[9]

URL https://arxiv.org/abs/2504.03832

Koch, T., Neira, D.E.B., Chen, Y ., Cortiana, G., Egger, D.J., Heese, R., Hegade, N.N., Cadavid, A.G., Huang, R., Itoko, T., Kleinert, T., Xavier, P.M., Mohseni, N., Montanez- Barrera, J.A., Nakano, K., Nannicini, G., O’Meara, C., Pauckert, J., Proissl, M., Ramesh, A., Schicke...

2025 arXiv
[11]

Ritter, H.: Aufz ¨ahlung von kurzen Gittervektoren in allgemeiner Norm. Ph.D. thesis, Universit¨at Frankfurt (1997) 5

1997
[12]

SIAM Journal on Computing10(3), 456–464 (1981)

Schroeppel, R., Shamir, A.: A T = O(2n/2), S = O(2n/4) algorithm for certain NP-complete problems. SIAM Journal on Computing10(3), 456–464 (1981). URLhttps://doi.org/ 10.1137/0210033

1981 doi
[13]

Wassermann, A.: Finding simple t-designs with enumeration techniques. J. Com- binatorial Designs 6, 79–90 (1998). URL https://doi.org/10.1002/(SICI) 1520-6610(1998)6:2<79::AID-JCD1>3.0.CO;2-S

1998 doi
[15]

Wassermann, A.: Search for combinatorial objects using lattice algorithms – revisited. In: P. Flocchini, L. Moura (eds.) Combinatorial Algorithms, pp. 20–33. Springer International Publishing, Cham (2021). URL https://doi.org/10.1007/978-3-030-79987-8_2

2021 doi
[16]

Wiley (1978) 6 Table 1: Computing results for instances from Quantum Optimization Benchmark Library [9]

Williams, H.P.: Model Building in Mathematical Programming. Wiley (1978) 6 Table 1: Computing results for instances from Quantum Optimization Benchmark Library [9]. Class [8] (sec) First (sec) All (sec) Number of solutions (3,20,50) 0.00 0.00 1, 3, 1, 2 (3,20,100) 0.00 0.00 1,...

1978
[613]

Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1995)

1995

Pith tools

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

[1] [8]

GPU accelerated variant of Schroeppel-Shamir's algorithm for solving the market split problem

Kempke, N.C., Koch, T.: GPU accelerated variant of Schroeppel-Shamir’s algorithm for solving the market split problem (2025). URL https://arxiv.org/abs/2507.05045

work page Pith review arXiv 2025

[2] [14]

Wassermann, A.: Attacking the market split problem with lattice point enumeration. J. Combinatorial Optimization 6, 5–16 (2002). URL https://doi.org/10.1023/A: 1013355015853

doi:10.1023/a: 2002

[3] [10]

Ogita, T., Rump, S.M., Oishi, S.: Accurate sum and dot product. SIAM J. Sci. Comput. 26(6), 1955–1988 (2005). URL https://doi.org/10.1137/030601818

doi:10.1137/030601818 2005

[4] [1]

Aardal, K., Bixby, R.E., Hurkens, C.A.J., Lenstra, A.K., Smeltink, J.W.: Market split and basis reduction: Towards a solution of the Cornu ´ejols-Dawande instances. In: R.E. 4 Burkard, G. Cornu ´ejols, G.J. Woeginger (eds.) Integer Programming and Combinatorial Optimization, 7th International IPCO Conference, pp. 1–16. Lecture Notes in Computer Science 16...

work page 1999

[5] [2]

Aardal, K., Hurkens, C.A.J., Lenstra, A.K.: Solving a linear diophantine equation with lower and upper bounds on the variables. In: R.E. Bixby, E.A. Boyd, R.Z. R ´ıos-Mercado (eds.) Integer Programming and Combinatorial Optimization, 6th International IPCO Con- ference, pp. 229–242. Lecture Notes in Computer Science 1412, Springer-Verlag, Heidel- berg (19...

work page doi:10.1007/3-540-69346-7_18 1998

[6] [3]

Japan Journal of Industrial and Applied Mathematics (2025)

Aono, Y ., Nguyen, P.Q.: On tiny-probability lattice enumeration. Japan Journal of Industrial and Applied Mathematics (2025). URL https://doi.org/10.1007/ s13160-025-00713-6

work page 2025

[7] [4]

In: Par- allel Virtual Machine – EuroPVM’96 (Munich, 1996), Lecture Notes in Comput

Betten, A., Wassermann, A.: {0,1}-solutions of integer linear equation systems. In: Par- allel Virtual Machine – EuroPVM’96 (Munich, 1996), Lecture Notes in Comput. Sci. , vol. 1156, pp. 311–314. Springer, Berlin (1995). URL https://doi.org/10.1007/ 3540617795_40

work page 1995

[8] [5]

Cornu ´ejols, G., Dawande, M.: A class of hard small 0-1 programs. In: R.E. Bixby, E. Boyd, R. R ´ıos-Mercado (eds.) Integer Programming and Combinatorial Optimiza- tion. 6th International IPCO Conference, Houston, Texas, June 1998. Springer Lecture Notes in Computer Science 1412, pp. 284–293. Springer-Verlag, Heidelberg (1998). URL https://doi.org/10.100...

doi:10.1007/3-540-69346-7_22 1998