Scaling up linear programming with PDLP

Classic linear programming (LP) problems are one of the most foundational problems in computer science and operations research. With extensive applications across numerous sectors of the global economy, such as manufacturing, networking, and other fields, LP has been the cornerstone of mathematical programming and has significantly influenced the development of today’s sophisticated modeling and algorithmic frameworks for data-driven decision making. If there's something to optimize, there's a good chance LP is involved.

Since the late 1940s, LP solving has evolved significantly, with the simplex method by Dantzig and various interior-point methods being the most prevalent techniques. Today's advanced commercial LP solvers utilize these methods but face challenges in scaling to very large instances due to computational demands. In response to this limitation, first-order methods (FOMs) have gained traction for large-scale LP problems.

With the above in mind, we introduce our solver PDLP (Primal-dual hybrid gradient enhanced for LP), a new FOM–based LP solver that significantly scales up our LP solving capabilities. Utilizing matrix-vector multiplication rather than matrix factorization, PDLP requires less memory and is more compatible with modern computational technologies like GPUs and distributed systems, offering a scalable alternative that mitigates the memory and computational inefficiencies of traditional LP methods. PDLP is open-sourced in Google’s OR-Tools. This project has been in development since 2018 [1, 2, 3], and we are proud to announce that it was co-awarded the prestigious Beale — Orchard-Hays Prize at the International Symposium of Mathematical Programming in July 2024. This accolade is one of the highest honors in the field of computational optimization, awarded every three years by the Mathematical Optimization Society.

LP and first-order methods for LP

Scaling the methods used in today’s state of the art LP solvers presents significant challenges. The primary computational limitations for both methods relate to matrix factorization required for solving linear equations, introducing two key challenges as problem sizes grow:

1. Memory overflows: LP solvers that use the simplex method (such as Google's GLOP) employ LU factorization, and solvers that use the interior point method use Cholesky factorization. For both these methods the resulting factorization uses considerably more memory than the LP instance itself.
2. Hardware-related challenges: Both methods face difficulties leveraging modern computing architectures, such as GPUs or distributed systems, because the sparse matrix factorization step usually requires highly sequential operations.

Given the above limitations associated with traditional LP methods, FOMs have emerged as a promising alternative for tackling large-scale LP problems. Unlike methods that rely on matrix factorization, FOMs utilize gradient information to iteratively update their solutions, with the primary computational requirement being matrix-vector multiplication. This distinction means that FOMs require only the storage of the LP instance itself, without needing additional memory to store factorized forms. Additionally, advances in FOMs for machine learning and deep learning have enhanced their scalability, making them highly efficient on modern computing platforms such as GPUs and distributed computing. This scalability and reduced memory dependency make FOMs particularly suitable for large and complex LP tasks where traditional methods may falter.

Restarted primal-dual hybrid gradient for LP

Primal-dual hybrid gradient (PDHG) is widely recognized for its application in image processing. When applied to LP, PDHG's primary computational demand involves matrix-vector multiplication, eliminating the need for matrix factorizations. This makes PDHG particularly efficient for large-scale computational tasks, but it is not reliable in solving LP. For example, in a benchmark of 383 instances, PDHG can only solve 113 instances to moderate accuracy.

To enhance PDHG’s reliability in solving LP problems, we have developed a modified approach called restarted PDHG. This version uses a two-loop structure where PDHG is run until a restarting condition is triggered, after which the average of the PDHG iterations is computed. The algorithm then restarts from this average point. This approach is visualized below where the trajectory of the standard PDHG is depicted with a blue line, the average iteration with a red line, and the restarted PDHG with a green line. Notably, the restarted PDHG shows a quicker convergence to the optimal solution, marked by a star on the plot.

PDLP

We designed PDLP as a software package that can solve linear programming problems efficiently. The core algorithm of PDLP is based on the restarted PDHG, which we have enhanced significantly through five improvements:

• Presolving: This process simplifies the LP problem before solving. It involves detecting inconsistent bounds, detecting duplicate rows, tightening bounds, etc. These steps reduce complexity and improve the efficiency of the solver.
• Preconditioning: A preconditioner in PDLP rescales variables and constraints within the LP instance. This adjustment helps speed up the algorithm by optimizing the numerical condition of the problem, thereby enhancing convergence rates.
• Infeasibility detection: In real-world scenarios, LP problems may often be infeasible or unbounded. Our approach utilizes the iterates of PDHG, which encodes information about the problem's feasibility and boundedness, allowing for detection without extra computational effort. The theory of this method is detailed in our SIAM Journal paper.
• Adaptive restarts: This technique involves strategically deciding when to optimally restart the PDHG algorithm to enhance its efficiency, particularly speeding up the convergence to a high-accuracy solution.
• Adaptive step-size: We introduced an adaptive method for selecting the step-size in the PDHG, which significantly reduces the need for manual tuning. This approach adjusts the step-size dynamically based on the problem's characteristics and the algorithm's performance, promoting faster convergence.

PDLP is open-sourced as part of Google’s OR-Tools, an open-source software suite for optimization. The solver is easy to use and it has interfaces in Python, C++, Java and C#. More details and examples on how to use PDLP can be found in the OR-Tools documentation.

Applications

Scaling up and speeding up LP enables new applications — here, we briefly mention three:

1. Data center network traffic engineering (blog post, paper): Google's data centers rely on dynamically optimized traffic engineering for high-performance efficiency. The challenge of optimizing network traffic routing is periodically addressed as a large-scale LP problem. Previously, solving this large problem fast enough was not possible, leading to the development of partition heuristics. These heuristics decomposed the problem into many smaller-scale LPs that could be solved concurrently, albeit at the cost of optimality. With the introduction of PDLP, we can now efficiently optimize traffic routing across an entire data center network, effectively saving a significant amount of machine resources across the network. This solution has been deployed in Google's production environment since May 2023.
2. Container shipping optimization (blog post): The world's shipping supply chain relies on optimizing the order in which vessels visit ports and the placement of containers on those vessels. Due to the extreme scale of real-world instances, a direct solution often is intractable. Consequently, various heuristic approaches have been proposed to enhance efficiency and practicality in solving this complex optimization problem. The problem can be formulated as a type of optimization problem called a massive integer two-layer multi-commodity flow problem. PDLP enables solving the linear relaxation of this formulation, quantifying the quality of the heuristics.
3. Traveling salesman problem: The traveling salesman problem (TSP) poses a classic question: given a list of cities and their distances, what's the shortest route that visits every city once and returns to the starting point? This problem is notoriously challenging, holding significant importance in theoretical computer science and operations research. PDLP has demonstrated its power by solving real-world TSP lower bound LP instances of immense scale, encompassing up to 12 billion non-zero entries in the constraint matrix. This capability far surpasses the capacity of even the most advanced commercial solvers available today, showcasing PDLP's potential for tackling large-scale LP challenges.

Broader impacts

Since its initial release, PDLP has attracted significant interest, leading to further enhancements. Here are some notable developments: cuPDLP.jl is an open-sourced GPU implementation of PDLP, written in Julia. The commercial solver company, Cardinal Optimizer, has incorporated PDLP into their software in Version 7.1 in January 2024. The open-source solver, HiGHS, has incorporated a version of PDLP in their software in V1.7.0 in March 2024. In addition, the academic community has continued to explore and expand upon the theoretical foundations of PDLP. Recent studies have focused on areas such as new analysis on PDHG, condition number theory, trajectory-based analysis, extensions to quadratic programming and semi-definite programming, etc. These efforts not only deepen the understanding of PDLP's underlying mechanics but also explore its potential applications to more complex problems. These developments reflect PDLP's significant impact on the field of optimization, bridging the gap between theoretical research and practical application. As PDLP continues to evolve, its influence is expected to grow, pushing the boundaries of what can be achieved in computational optimization.

Acknowledgments

We are grateful to our co-authors Mateo Diaz, Oliver Hinder, Miles Lubin, Brendan O’Donoghue, and Warren Schudy for their exceptional support and contributions. We would also like to thank our managers, Vahab Mirrokni, Jon Orwant and Aaron Archer, and our collaborators in the Data Center Networking team, the Algorithm and Optimization team and the Operations Research team.