GPU-Accelerated Primal Heuristics for Mixed Integer Programming
Akif Çördük, Piotr Sielski, Alice Boucher, Kumar Aatish · 2025
Read GPU-Accelerated Primal Heuristics for Mixed Integer Programming by Akif Çördük, Piotr Sielski, Alice Boucher, Kumar Aatish (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20499.txt.
Introduction
Akif Çördük, Piotr Sielski, Alice Boucher, and Kumar Aatish combine several graphics-processor-accelerated primal heuristics for mixed integer programming. Graphics acceleration allows larger search regions and faster iterations when hunting for good feasible solutions. A GPU version of a primal-dual linear method serves as an approximate linear programming solver, while a new probing cache speeds up roundings and detects infeasibility early.
Well-known heuristics including Feasibility Pump, Feasibility Jump, and Fix-and-Propagate are further accelerated and enhanced on the graphics hardware. On the MIPLIB2017 benchmark over a presolved dataset, the combined approach finds two hundred twenty-one feasible solutions and reaches a twenty-two percent objective gap. The authors report significant gains over existing methods in both solution count and objective quality.
Catalog record
| CREATOR | Akif Çördük, Piotr Sielski, Alice Boucher, Kumar Aatish |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-20499
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
GPU-Accelerated Primal Heuristics for Mixed Integer Programming Akif Çördük, Piotr Sielski, Alice Boucher, Kumar Aatish Abstract We introduce a fusion of GPU accelerated primal heuristics for Mixed Integer Programming. Leveraging GPU acceleration enables exploration of larger search regions and faster iterations. A GPU-accelerated PDLP serves as an approximate LP solver, while a new probing cache facilitates rapid roundings and early infeasibility detection. Several state-of-the-art heuristics, including Feasibility Pump, Feasibility Jump, and Fix-and-Propagate, are further accelerated and enhanced. The combined approach of these GPU-driven algorithms yields significant improvements over existing methods, both in the number of feasible solutions and the quality of objectives by achieving 221 feasible solutions and 22% objective gap in the MIPLIB2017 benchmark on a presolved dataset. \workshoptitle ScaleOPT: GPU-Accelerated and Scalable Optimization 1 Introduction Mixed Integer Linear Programming (MILP) problem is a mathematical optimization problem defined as a Linear Programming problem with an additional requirement that some of the variables must be integers. MILP is a generalization of NP-hard [ 12 ] Integer Programming and is defined as follows: Minimize \displaystyle\sum_{i=1}^{p}c_{i}x_{i}+\sum_{j=p+1}^{n}d_{j}y_{j} subject to \displaystyle\sum_{i=1}^{p}a_{ki}x_{i}+\sum_{j=p+1}^{n}b_{kj}y_{j}\leq g_{k},\quad\forall k\in\{1,\dots,m\} \displaystyle x_{i}\in[l_{i},u_{i}],\quad\forall i\in\{1,\dots,p\}\quad y_{j}\in[l_{j},u_{j}],\quad\forall j\in\{p+1,\dots,n\} \displaystyle y_{j}\in\mathbb{R},\quad x_{i}\in\mathbb{Z}\quad c_{i},d_{j},a_{ki},b_{kj},g_{k}\in\mathbb{R} Currently, the state-of-the-art method for solving MILP problems to optimality is the Branch and Cut which works by enumerating the tree of all possibilities (Branching) and strengthening the formulation by adding cutting planes at tree nodes. During the process of tree exploration, many branches can be fathomed. One of the possibilities of fathoming is by comparing the objective of the best incumbent solution with the dual bound of the branch. Such a solution may be obtained by using various primal heuristic methods- methods that focus on finding strong feasible solutions without a proof of optimality. In many cases the MILP problem is too hard to solve to optimality in a given time budget, in which case the primal heuristics serve as one of the main tools for finding good feasible solutions. Significant efforts have been made in recent years to improve such methods [ 18 , 14 , 13 , 1 , 7 , 4 , 5 ] . Feasibility Pump(FP) is the most commonly heuristics that uses sequence of projections and roundings. The projections minimize the L1 distance of integer variables to the polytope which has a converging behavior that the sum of L1 distances decrease over iterations. When the distance of the projection is zero, an integer feasible solution is found. Often, projection and rounding enter a cycle that is broken by various methods, including perturbation [ 8 ] and the WalkSat algorithm [ 6 , 20 ] . Various versions of FP has been proposed, some of which use objective components [ 1 ] and two-stage runs starting from binary variables first by relaxing the other integer variables [ 4 ] . As rounding heuristics, one of the state-of-the-art methods is the fix-and-propagate [ 18 ] which does a sequence of variable fixing (rounding the variable and fixing its bounds to the rounding) and bounds propagation(BP). The authors handle the infeasibility in two ways, backtracking and repair procedure which does a neighborhood search by shifting the variable bounds to minimize constraint violation. We propose a fusion of methods that work together to achieve a higher number of feasible solutions and better objective than the state-of-the-art methods. The proposed framework, which is an improved FP, includes strategic use of the Local-MIP [ 13 ] to break cycles in the FP and also to search a neighborhood of an integer point. We also improve fix-and-propagate by introducing a new method of bulk rounding which uses a probing cache. In addition, we provide efficient GPU implementation of bound propagation algorithm with double probing, load balancing and propagation on changed constraints. We also introduce variable rounding order prioritization on new criterion. The PDLP algorithm is used in the beginning and in FP projections with approximate results and warm starts [ 16 , 2 , 15 ] that allows faster iterations. All methods are parallelized and implemented on Nvidia CUDA. The whole framework and the code base is open source and accessible at Nvidia cuOpt Github repository [ 17 ] . 2 GPU Algorithms 2.1 Bound Propagation The bound propagation(BP) [ 19 ] is a two step iterative process for tightening the bounds of variables. In every iteration, the minimal and maximal constraint activities are calculated for every constraint k : \displaystyle\sum_{i=1}^{n}a_{ki}z_{i}\leq g_{k}\quad\text{where}\quad \displaystyle z_{i}\in[l_{i},u_{i}]\quad L^{k}_{min}=\sum_{\begin{subarray}{c}i\in\mathbb{N}\\ a_{ki}>0\end{subarray}}a_{ki}l_{i}+\sum_{\begin{subarray}{c}i\in\mathbb{N}\\ a_{ki}<0\end{subarray}}a_{ki}u_{i} The activity values, along with the current variable bounds are used to tighten the bounds further for every variable i : \hat{l_{i}}=\max_{k\in\mathbb{N}}\{\frac{g_{k}-L^{k}_{min}+a_{ki}u_{i}}{a_{ki}}:a_{ki}<0\},\quad\hat{u_{i}}=\min_{k\in\mathbb{N}}\{\frac{g_{k}-L^{k}_{min}+a_{ki}l_{i}}{a_{ki}}:a_{ki}>0\} If the bound updates do not cross a threshold, the iterations are terminated. In the MIPLIB2017 [ 9 ] instances, the median of average number of terms per constraint or variable was found to be in the range 6-9. We also see a substantial variability in the number of terms across the dataset. This observation motivates us to specialize our approach tailored to the number of non-zero terms for a constraint or a variable similar to [ 21 ] but we go a few steps further. We create a load balanced version of the problem statement using Logarithmic Radix Binning [ 10 ] . Constraints with similar number of non-zero terms are binned together in global memory to form a Compressed Sparse Row(CSR). A similar operation is done for each variable to obtain a load balanced version of the CSR transpose. The activity and bounds update calculation is done via three different approaches. For activity calculation, the sub-warp approach splits each warp to work on multiple small constraints at once. Each warp accesses the binning offsets generated by LRB and determines the bin assigned to it. This information, along with the warp id helps in calculating which constraints the warp is operating on and how the warp should be split to handle the multiple constraints at once. This approach allows us to work on all the coefficient and variable index data brought in to the cache. The block approach works on medium sized constraints where a single thread block is sufficient to operate on a constraint. The third, heavy element approach splits every large constraint (greater than 16k terms) to be dealt by multiple blocks. The partial summations of activities calculated by each block are written to a global temporary array. A second pass summation is then run to reach the final activity values of the heavy constraints. A similar approach is utilized for bounds update step, where the summation is replaced with minimum and maximum operators. In both the steps while the CSR information is loaded into memory in a coalesced fashion, random accesses to two values for each non-zero term is necessary, i.e. in the activity calculation requires variable lower and upper bound, and bounds update requires the minimal and maximal activity. In order to improve cache performance, the variable bounds are grouped together into a single buffer so that the lower and upper bounds of variable i are at location 2i and 2i+1 . A single buffer is maintained for the activities as well. CUDA graphs have been utilized to reduce kernel launch latency and run the three approach concurrently. 2.2 Probing Cache For a binary variable, the implications derived from