Solving the Market Split Problem with Lattice Enumeration
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909733954256896 |
|---|---|
| author | Wassermann, Alfred |
| author_facet | Wassermann, Alfred |
| contents | The market split problem was proposed by Cornuéjols 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.
The market split problem seems to be difficult to solve with the conventional branch-and-bound 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 short note we report about experiments with our algorithm that reduces the market split problem to a lattice problem. The author's most recent implementation solvediophant applied to the QOBLIB market split instances can solve instances up to $m=14$ on a standard computer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08702 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Solving the Market Split Problem with Lattice Enumeration Wassermann, Alfred Optimization and Control 90C27, 90-08, 90-04 The market split problem was proposed by Cornuéjols 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. The market split problem seems to be difficult to solve with the conventional branch-and-bound 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 short note we report about experiments with our algorithm that reduces the market split problem to a lattice problem. The author's most recent implementation solvediophant applied to the QOBLIB market split instances can solve instances up to $m=14$ on a standard computer. |
| title | Solving the Market Split Problem with Lattice Enumeration |
| topic | Optimization and Control 90C27, 90-08, 90-04 |
| url | https://arxiv.org/abs/2508.08702 |