10319 2026 eng conferenceobject 0 -- -- -- The market split problem (MSP), introduced by Cornu´ejols and Dawande (1998), is a challenging binary optimization problem on which state-of-the-art linear programming-based branch-and-cut solvers perform poorly. We present a novel algorithm for solving the feasibility version of this problem, derived from Schroeppel–Shamir’s algorithm for the one-dimensional subset sum problem. Our approach is based on exhaustively enumerating one-dimensional solutions of MSP and utilizing GPUs to evaluate candidate solutions across the entire problem. The resulting hybrid CPU-GPU implementation significantly outperforms a parallel CPU-only variant, efficiently solving instances with up to 10 constraints and 90 variables. We demonstrate the algorithm’s performance on benchmark problems, solving instances of size (9, 80) in less than fifteen minutes and (10, 90) in up to one day. Given our results, sorting based algorithms can be considered competitive for solving the MSP on modern hardware. Operations Research Proceedings 2025 2507.05045 yes accepted for publication 2026-02-20 publish urn:nbn:de:0297-zib-100554 false true Nils-Christian Kempke Nils-Christian Kempke Thorsten Koch OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING Koch, Thorsten MODAL-Gesamt Mathematical Algorithmic Intelligence MODAL-EnergyLab Kempke, Nils-Christian Applied Optimization