Solve Linear Programs Using the GPU-Accelerated Barrier Method in NVIDIA cuOpt

How does the NFL schedule all its regular-season games while avoiding stadium conflicts with Beyoncé live shows?  

How can doctors use a single donated kidney to trigger a sequence of transplants, and the way do they create the longest possible transplant chain to avoid wasting essentially the most patients?

How do airlines plan flight crew schedules around rest requirements and crew locations while minimizing hotel and deadheading costs?

Most of these problems might be solved using optimization, a branch of applied mathematics that uses linear programming (LP) and mixed integer programming (MIP) to seek out optimal solutions. Nevertheless, solving such problems isn’t easy because they often contain hundreds of thousands of variables and constraints that may slow CPUs. Approximate solutions can sometimes be found quickly, but finding highly accurate solutions takes longer. 

NVIDIA cuOpt is an open source GPU-accelerated library for solving optimization problems. The most recent cuOpt release features a latest solver for linear programs that uses the barrier method. This latest solver complements the present cuOpt LP solvers, enabling engineers, researchers, and developers to unravel large-scale linear programs quickly and accurately.

Internal benchmarks show cuOpt barrier delivering over 8x average speedup in comparison with a number one open source CPU solver and over 2x average speedup in comparison with a preferred business CPU solver on a public test set of enormous linear programs (Figure 1).

When cuOpt barrier is combined with cuOpt PDLP in concurrent mode, it ranked first amongst open source solvers and second overall out of 11 solvers in public benchmarks (retrieved October 20, 2025).

This post explains the fundamentals of linear programs, introduces the brand new cuOpt GPU-accelerated barrier method, and dives deeper into the benchmark data on its performance.

What are linear programming and mixed integer programming? 

Linear programming is a way for solving optimization problems where a linear objective function is minimized subject to linear constraints. A wide selection of applications might be forged as linear programs, akin to mixing and mixing problems in food and chemical production, transportation, network flow problems, and portfolio optimization in finance.

Linear programming also plays a vital role in mixed integer programming, a way for solving optimization problems where some variables tackle integer, or whole number, values. Mixed integer programming is a vital tool in the sector of operations research that enables practitioners to unravel problems with discrete decisions. There are lots of applications of mixed integer programming, including:

How are linear programs solved?

There are three essential methods for solving linear programs: simplex, PDLP, and barrier.

• Simplex: The classical algorithm for solving linear programs is the simplex method, invented by George Dantzig in 1947. Simplex continues to be widely used today and cuOpt includes an implementation of the twin simplex algorithm.
• PDLP: A brand new first-order method that exploits the GPU was recently introduced called Primal-Dual Hybrid Gradient for Linear Programming (PDLP).
• Barrier: Within the Nineteen Nineties, a brand new class of algorithms for linear programming emerged called barrier or interior-point methods. Barrier methods are theoretically proven to unravel linear programs in polynomial time. An algorithm developed by Sanjay Mehrotra called the predictor-corrector method is utilized in open source and business solvers. In practice, these methods often take somewhere between 20 and 200 iterations to seek out an answer, no matter the scale of the issue. Each iteration requires multiple sparse systems of linear equations to be solved. 

Each method excels in numerous problems and in numerous use cases (Table 1). 

Method	When to make use of
Simplex	–Best for small to medium LPs –Requires a factorization to suit into memory –Produces the highest-accuracy solutions –Solutions lie at a vertex of the feasible region
PDLP	–Fast on large LPs –No factorization required –Low-accuracy solutions have to be acceptable
Barrier	–Fast on large LPs –Requires a factorization to suit into memory –Produces high-accuracy solutions

How does cuOpt solve linear programs?

When using cuOpt, you don’t need to decide on which method to unravel linear programs. By default, cuOpt runs all three algorithms concurrently and provides the answer from the strategy that finishes first.

cuOpt comprises an implementation of PDLP that may in a short time solve LPs to low accuracy (a relative tolerance of 1e-4 to 1e-6, for instance). Nevertheless, many applications of linear programming require more accurate solutions (a relative tolerance of 1e-8 or an absolute tolerance of 1e-6, for instance).

Previously, when a cuOpt user required a highly accurate solution, the one option was to make use of the simplex algorithm. While the simplex algorithm is well-suited for small- to medium-scale LPs, it will possibly struggle on large-scale LPs. 

With the introduction of the brand new barrier method, cuOpt extends its high-performance GPU-accelerated LP solvers to large-scale LPs where high accuracy is required. 

How does the cuOpt GPU-accelerated barrier solver work?

The cuOpt barrier method uses the identical well-proven predictor-corrector algorithm developed by researchers within the Nineteen Nineties, following the book Primal-Dual Interior-Point Methods and the paper On Implementing Mehrotra’s Predictor-Corrector Interior-Point Method for Linear Programming.

The predictor-corrector method requires solving multiple sparse systems of linear equations at each iteration. Until recently, these were solved using multi-threaded algorithms on the CPU. This modified with the discharge of NVIDIA cuDSS, the NVIDIA GPU-accelerated sparse direct-solver library. cuDSS significantly outperforms CPU algorithms. cuDSS enabled the cuOpt team to bring the Mehrotra predictor-corrector algorithm to the GPU. 

The most recent release, cuDSS 0.7, includes several enhancements developed specifically for cuOpt:

• Faster symbolic factorization: On average, symbolic factorization is now 2.5x faster over a test set of optimization matrices.
• Choice to stop cuDSS reordering and symbolic factorization phases: This is useful when running concurrently with algorithms like PDLP and simplex.
• Deterministic mode: cuDSS 0.7 features a bit-wise deterministic mode. This enables cuOpt to be reproducible, returning equivalent results given the identical inputs.

Along with cuDSS, cuOpt uses cuSPARSE to perform sparse matrix-matrix multiplication and sparse matrix-vector multiplications efficiently on the GPU.

How does the cuOpt barrier method compare to open source and business CPU solvers? 

Performance of the brand new cuOpt barrier method was measured over a publicly available test set of 61 linear programs maintained by Hans Mittelmann at Arizona State University. For details, see Benchmarks for Optimization Software.

The linear programs on this test set are large. Figure 2 shows the distribution of those problems by way of the variety of variables and constraints—each dot represents an LP. This test set has a few dozen problems with greater than 1 million variables and constraints.

Experimental setup

Runtime was compared for the cuOpt barrier method versus several CPU solvers. All solvers were run on an NVIDIA GH200 Grace Hopper machine with 72 3.4GHz CPU cores, 500 GB of RAM, and an NVIDIA H200 GPU with 480 GB of VRAM. Each solver was configured to run the barrier method without crossover; all other settings were taken as default. All problems were run with a closing date of 1 hour. If a solver failed to unravel an issue, the runtime was taken to be one hour. 

How does the cuOpt barrier method compare to an open source CPU solver?

Within the test set, cuOpt solves 55/61 problems, and the open source solver solves 48/61 problems. On average (geometric mean) over the test set, cuOpt is quicker than the open source solver by 8.81x. 

Figure 3 shows the speedup of the cuOpt barrier method in comparison with the open source solver for every of the 61 problems within the Mittelmann test set on NVIDIA GH200. Each bar represents the open source solver runtime divided by the cuOpt runtime on a specific model. Bars greater than 1 (in green) represent LPs where cuOpt is quicker. Bars lower than 1 (in gray) represent LPs where the open source solver is quicker. 

How does the cuOpt barrier method compare to business CPU solvers?

cuOpt was also measured against two leading business solvers. The experimental setup was the identical as previously described: all solvers were run using the barrier method without crossover and default settings. 

Business CPU solver A

On 31/61 problems within the test set, cuOpt is quicker than the business solver. On seven problems, cuOpt is greater than 5x faster than the business solver—with a maximum speedup of 17x. Nevertheless, on average (geometric mean), business solver A is 1.5x faster over the entire test set. This is probably going attributable to the subtle presolve methods utilized by business solver A. cuOpt doesn’t have an intensive presolve. Business solver A solves 60/61 problems within the test set.

Business CPU solver B

cuOpt does higher against one other popular business CPU solver B. On average (geometric mean) over the test set, cuOpt is 2x faster than business solver B.

This business solver solved 58/61 problems within the test set.

Start with the NVIDIA cuOpt barrier method

The cuOpt open source solver helps solve large-scale LPs quickly and accurately. You possibly can now run simplex, PDLP, and barrier in your largest and most difficult linear programs.

To start, visit the cuOpt Barrier Notebook to learn tips on how to install cuOpt 25.10, run the brand new barrier method, and use necessary settings like presolve and folding. 

Download cuOpt 25.10 and run it in your hardest linear programs to see the way it compares with other solvers.