95. A GPU accelerated variant of Schroeppel-Shamir's algorithm for solving the market split problem
Invited abstract in session TC-2: Integer Programming I, stream Discrete and Combinatorial Optimization.
Thursday, 11:45-13:15Room: H4
Authors (first author is the speaker)
| 1. | Thorsten Koch
|
| Applied Algorithmic Intelligence Methods, ZIB / TU Berlin | |
| 2. | Nils-Christian Kempke
|
| Software und Algorithmen für die diskrete Optimierung, Technische Universität Berlin |
Abstract
The market split problem, as 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 the market split problem. It is derived from the Schroeppel–Shamir algorithm for the one-dimensional subset sum problem and is based on the exhaustive enumeration of all one-dimensional solutions of the market split problem. We utilize GPUs to efficiently evaluate these one-dimensional candidate solutions across the entire problem, yielding a hybrid CPU-GPU implementation capable of efficiently solving instances of the market split problem with up to 10 constraints and 90 variables. We demonstrate our algorithm’s performance on a set of benchmark problems, solving instances of size (9, 80) in less than fifteen minutes and (10, 90) in under one day.
Keywords
- Combinatorial Optimization
Status: accepted
Back to the list of papers