标题： 用格枚举求解市场分割问题 显示英文标题

标题： Solving the Market Split Problem with Lattice Enumeration

摘要： 市场分割问题由Cornuéjols和Dawande于1998年提出，作为求解具有二进制变量的线性系统算法的基准问题。最近（2025年）的量子优化基准库（QOBLIB）包含了一组可行的市场分割问题实例。市场分割问题似乎很难用整数线性规划软件的传统分支定界方法解决，据报道该方法可以处理QOBLIB中的实例最多到$m=7$。相反，一种新的Schroeppel-Shamir算法的GPU实现可以解决到$m=11$的实例。在这篇简短的注释中，我们报告了我们算法的实验，该算法将市场分割问题转化为格问题。作者最近的实现diophant应用于QOBLIB市场分割实例可以在标准计算机上解决到$m=14$的实例。 显示英文摘要

摘要： 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. 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.