Abstract: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. 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.
From: Alfred Wassermann [view email]
[v1]
Tue, 12 Aug 2025 07:46:04 UTC (8 KB)
[v2]
Thu, 25 Jun 2026 16:54:45 UTC (42 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。