Market Split
Overview
The Market Split Problem is a multi-dimensional variant of the classic subset sum problem, where multiple constraints must be satisfied simultaneously. Each row represents its own subset sum problem, making this a challenging combinatorial optimization task.
Problem Description
Given a matrix $A \in \mathbb{N}^{m,n}$ and a right-hand side vector $b \in \mathbb{N}^m$, find a feasible binary vector $x \in \{0,1\}^{n}$ that satisfies:
$$ Ax = b $$
where each row $i \in \{1,\ldots,m\}$ represents an independent subset sum constraint that must be fulfilled simultaneously.
Performance
Runtime to reach best-known objective
Sorted instances vs total runtime. A point (x, y) means x instances were solved within y seconds. Solid line + filled circle = proven exact; dashed line + open diamond = heuristic. Lower-right is better.
Time-to-solution (TTS) to reach best-known objective
Same as the runtime cactus but uses the reported Time-to-Solution rather than total runtime. Solid = exact, dashed = heuristic.
Runtime scaling with instance size
Fastest feasible runtime (log scale) per instance versus Variables — shows how each group scales.
Submissions
(6)
| Method | Submitter | Type | Date | Instances |
|---|---|---|---|---|
| Parity_Twine | ParityQC Team | Quantum HW | 2026-07-28 | 10 |
| SA | Q-Bridge Team | Classical | 2026-07-09 | 4 |
| Arvak | Daniel Hinderink | Quantum sim | 2026-03-08 | 1 |
| Lattice | Alfred Wassermann | Classical | 2025-07-15 | 115 |
| MIP | Maximilian Schicker | Classical | 2024-12-23 | 60 |
| Abs2 | Maximilian Schicker | Classical | 2024-12-22 | 60 |