Solving the market split problem with lattice enumeration

Titelangaben

Wassermann, Alfred:
Solving the market split problem with lattice enumeration.
In: Mathematical Programming Computation. (4 Juni 2026) .
ISSN 1867-2957
DOI: https://doi.org/10.1007/s12532-026-00328-z

Volltext

Link zum Volltext (externe URL):

Angaben zu Projekten

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.