GFORS: GPU-Accelerated First-Order Method with Randomized Sampling for Binary Integer Programs
Preprint
Abstract
We present GFORS, a GPU-accelerated framework for large binary integer programs. It couples a first-order (PDHG-style) routine that guides the search in the continuous relaxation with a randomized, feasibility-aware sampling module that generates batched binary candidates. Both components are designed to run end-to-end on GPUs with minimal CPU-GPU synchronization. The framework establishes near-stationary-point guarantees for the first-order routine and probabilistic bounds on the feasibility and quality of sampled solutions, while not providing global optimality certificates. To improve sampling effectiveness, we introduce techniques such as total-unimodular reformulation, customized sampling design, and monotone relaxation. On classic benchmarks (set cover, knapsack, max cut, 3D assignment, facility location), baseline state-of-the-art exact solvers remain stronger on small-medium instances, while GFORS attains high-quality incumbents within seconds; on large instances, GFORS yields substantially shorter runtimes, with solution quality often comparable to -- or better than -- the baseline under the same time limit. These results suggest that GFORS can complement exact solvers by delivering scalable, GPU-native search when problem size and response time are the primary constraints.Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problemsComputational Optimization and Applications, 2021
- OSQP: an operator splitting solver for quadratic programsMathematical Programming Computation, 2020
- Progress in presolving for mixed integer programmingMathematical Programming Computation, 2015
- Accelerated gradient methods for nonconvex nonlinear and stochastic programmingMathematical Programming, 2015
- The unconstrained binary quadratic programming problem: a surveyJournal of Combinatorial Optimization, 2014
- A First-Order Primal-Dual Algorithm for Convex Problems with Applications to ImagingJournal of Mathematical Imaging and Vision, 2010
- Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxationsMathematical Programming, 2008
- Exploring relaxation induced neighborhoods to improve MIP solutionsMathematical Programming, 2004
- Linear Time Algorithms for Knapsack Problems with Bounded WeightsJournal of Algorithms, 1999
- Cutting planes for integer programs with general integer variablesMathematical Programming, 1998