<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>10055</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2025-07-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A GPU accelerated variant of Schroeppel-Shamir's algorithm for solving the market split problem</title>
    <abstract language="eng">The market split problem (MSP), introduced by Cornuéjols and Dawande (1998), is a challenging binary optimization problem that performs poorly on state-of-the-art linear programming-based branch-and-cut solvers. 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 efficiently solves 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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-100554</identifier>
    <identifier type="arxiv">2507.05045</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Nils-Christian Kempke</author>
    <submitter>Nils-Christian Kempke</submitter>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>25-10</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="persons" number="kempke">Kempke, Nils-Christian</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/10055/GPU_accelerated_Shroeppel_Shamir_ZibReport.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/10055/GPU_accelerated_Shroeppel_Shamir.pdf</file>
  </doc>
</export-example>
