By Dr. Cara Touretzky and Dr. Robert Luce
Gurobi is excited for the open-source release of cuOpt’s PDLP, which will help bring more GPU-friendly algorithms to linear programming. We also look forward to understanding how other parts of cuOpt might help optimization users.
To showcase how Gurobi and NVIDIA are collaborating under cuOpt, we’ve summarized our initial efforts in the space of GPU-accelerated optimization and the outlook for the optimization industry with these open-source tools.
For decades, two algorithmic powerhouses have dominated the field of linear programming (LP): the Simplex Method and Interior Point Methods (IPMs). These algorithms have been refined and improved for decades, and they remain powerful, reliable workhorses in optimization. However, leveraging GPU acceleration for these methods presents significant challenges.
A new approach—first-order methods—has emerged as a complementary option for large-scale LP problems (see this landmark paper) where traditional methods do not perform very well.
Unlike Simplex and IPMs, which rely on heavy linear algebra operations (such as matrix factorizations, pivoting, triangular substitution, etc.), first-order methods take a different approach, using gradient-based updates that rely on computationally lighter operations, like sparse matrix-vector multiplications. It’s this simplicity that allows for highly efficient implementations on the GPU, effectively paving the way for a transformation in the way large-scale LPs are solved.
Recognizing the potential of first-order methods, Gurobi has developed and integrated an experimental primal-dual hybrid gradient (PDHG)-type algorithm into its Optimizer. We’ve implemented this algorithm in two flavors:
From our internal benchmarks, we’ve seen that on certain large-scale, real-world problems, already the CPU-based algorithm can be competitive with our highly developed and optimized Simplex and IPM implementations. This advantage is magnified by our GPU-based PDHG implementation: Higher memory bandwidth on the GPU compared with the CPU’s memory system directly translates into a big performance improvement. Combining this algorithm with our other solver components—like presolve and crossover—can yield optimal, highly accurate solutions in relatively little time on some large-scale instances.
These results are still early—we like to think of them as a proof of concept. But we’re excited, because we know that we’re just at the beginning of a development curve where a new algorithmic option may open new opportunities in real-world optimization applications. With more focused engineering, more giant LP models available for testing, and more feedback from our customers and the community, we think that the potential of first-order methods will result in tangible benefits for users of optimization applications.
Our journey into GPU-accelerated, first-order methods has reinforced one key lesson: performance hinges on every implementation detail. From optimizing memory transfer patterns to implementing CUDA kernels efficiency, getting it right at the engineering level is essential for achieving the performance our customers expect.
That’s why we’re excited to see NVIDIA’s intent to open-source the PDLP component of the cuOpt library. With the breadth and efficiency of the CUDA framework, NVIDIA is the undisputed leader in delivering GPU-accelerated computing libraries, and sharing their engineering expertise for PDLP means that the commercial solver industry, open-source optimization solvers, and academic research groups all can learn from the best in class. The open availability will definitively spark further research on methods like PDLP, refining first-order algorithms for next-level performance.
We also believe that making optimization algorithms open source is beneficial for the entire ecosystem of optimization solution vendors and customers. It boosts visibility, encourages more researchers and practitioners to get involved, and ultimately builds trust in the tools that real-world optimization applications depend on.
We applaud NVIDIA’s decision to open-source cuOpt’s PDLP implementation, and look forward to continued collaboration, learning, and innovation. Together, we can push the boundaries of large-scale optimization and deliver faster, more efficient solutions for real-world challenges.
With Gurobi’s decision intelligence technology, customers can make optimal business decisions in seconds. From workforce scheduling and portfolio optimization to supply chain design and everything in between, Gurobi identifies the optimal solution, out of trillions of possibilities.
As the leader in decision intelligence, Gurobi delivers easy-to-integrate, full-featured software and best-in-class support, with an industry-leading 98% customer satisfaction rating.
Founded in 2008, Gurobi has operations in the Americas, Europe, and Asia. It serves customers in nearly all industries, including organizations like SAP, Air France, and the National Football League. For more information, please visit https://www.gurobi.com/ or call +1 713 871 9341.
Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.
Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.