Learn How NVIDIA cuOpt Accelerates Mixed Integer Optimization using Primal Heuristics

A MIP is a component of a category of NP-hard problems, meaning that no known algorithm can solve all such problems quickly within the worst case. Nonetheless, despite their NP-hardness, industrial MIP solvers routinely deliver optimal solutions for a lot of large instances. 

But certain problems remain intractable or require prolonged computation times. On condition that MIP models real-world problems and infrequently maps on to operational costs, it has been a longstanding goal—dating back to the mid-Twentieth century—to develop algorithms able to efficiently solving increasingly large and complicated instances. Significant theoretical and computational breakthroughs have been made since then, including the branch and certain algorithm, cutting planes, primal heuristics just like the feasibility pump, and, more recently, parallel processing. 

Real-world problems are typically dynamic, with inputs that change over time. This requires solvers to make use of iterative and incremental approaches, making speed essential at every step.  Time-critical MIPs include flexible job-shop scheduling and variants, lot sizing, and airline or railway crew scheduling. Consequently, in cuOpt, significant effort has been dedicated to developing primal heuristics for the invention of high-quality solutions inside a temporary timeframe— often faster than another open-source solver.

How you can get high-quality feasible solutions for MIPs

Some of the successful primal heuristics up to now is the feasibility pump (FP), with recent papers based on the thought emerging yearly. The predominant idea is comparatively easy: iterate between projections onto the feasible region and rounding variables that remain fractional using domain propagation. 

We  began by improving the present algorithms to maximise GPU performance and address two predominant bottlenecks of the FP algorithm:

1.  The projection is modeled as a Linear Programming problem.
2.  Domain Propagation after the projection 

We observed that the precision of the projection within the FP algorithm isn’t that vital, as we obtained similar results even with lower precision. This gave us the concept a first-order method may very well be used as an alternative of the simplex algorithm, and fortunately, the PDLP(Primal-Dual hybrid gradient)  was already implemented within the cuOpt framework. 

We warm-start the PDLP algorithm with the primal and dual solutions of the previous projection. Using PDLP within the FP, in addition to at the foundation node, enabled us to iterate much faster and solve larger problems more effectively. To tackle the second bottleneck, we implemented a GPU version of the domain propagation algorithm with significant improvements, reminiscent of bulk rounding and dynamic variable rating. After removing these bottlenecks, our focus shifted to removing cycling inside FP. 

Cycling is the issue of repeating steps, and is normally solved by introducing randomness to explore different regions of the search space. As an alternative, we opted for using the Local-MIP algorithm to interrupt the cycle and, at the identical time, improve the target. To do it efficiently,  Local-MIP was implemented on the GPU, outperforming the usual CPU version. 

We also added the target cutoff at every iteration and located a brand new best-feasible solution. We’ve published a paper detailing this. 

These improvements led to a complicated primal heuristic for locating feasible solutions. The next table shows a comparison of our method with a recent FP variant and the Local-MIP by way of the variety of feasible solutions (average over 3 runs) and the target gap (normalized difference between the optimal solution and the one found by our heuristics):

Along with these enhancements, we introduced three novel evolutionary algorithms to further refine the model. The evolutionary algorithms, applied upon detection of stagnation, effect a further 3% reduction within the primal gap. The incorporation of an easy Branch and Certain approach (excluding cutting planes) with diving threads and a subMIP-based Evolutionary Algorithm provided an excellent greater degree of improvement. We now proceed to check this method with the widely used open-source solvers:

MIP solvers benchmarks

The graphs show a considerable speedup in comparison with solvers that incorporate sophisticated cutting plane algorithms and problem-specific methodologies. This means potential for further improvement, in addition to the opportunity of augmenting any existing solver with the GPU-accelerated primal heuristics detailed previously.

How GPUs make MIP solving practical

Fast, feasible MIP solving plays a critical role in decision intelligence pipelines. When integrated with systems reminiscent of Palantir Ontology and NVIDIA Nemotron reasoning agents, it enables scenario generation and evaluation across many operational models in parallel. The open source GPU-accelerated MIP solver in cuOpt computes feasible solutions inside seconds, enabling downstream agents to simulate alternatives and re-optimize plans as conditions change. This capability turns static optimization right into a continuous feedback process for supporting adaptive decision making at scale.

Start with the MIP heuristics solver 
MIP heuristics offer fast and feasible solutions without exhaustively exploring the issue space. This permits organizations to quickly test alternatives and reply to real-world disruptions, reminiscent of port delays, equipment failures, or sudden demand spikes. NVIDIA cuOpt uses GPU acceleration to make these heuristics practical at scale, producing faster solutions, reducing objective gaps, and enabling continuous, adaptive decision-making pipelines. Explore the NVIDIA cuOpt GitHub to experiment and take a look at out examples of MIP use cases on your optimization problems.