Google’s PDLP Solver Revolutionizes Linear Programming Problem Solving Efficiency

Google researchers have developed a new algorithm called PDLP, which significantly improves the efficiency of solving large-scale linear programming (LP) problems. LP is a fundamental problem in computer science and operations research, with applications in fields such as data center network traffic engineering, container shipping optimization, and the traveling salesman problem. The PDLP algorithm uses preconditioning, infeasibility detection, adaptive restarts, and adaptive step size to speed up convergence rates.

This open-sourced solver is part of Google’s OR-Tools software suite and has Python, C++, Java, and C# interfaces. PDLP has already been deployed in Google’s production environment for data center network traffic engineering and has enabled the solution of massive LP instances that were previously intractable. The development of PDLP has also led to further enhancements, including a GPU implementation and incorporation into commercial solvers such as Cardinal Optimizer and HiGHS.

At its core, PDLP leverages the restarted Primal-Dual Hybrid Gradient (PDHG) algorithm, which has been significantly enhanced through five key improvements. These refinements have transformed PDLP into a highly efficient and theoretically sound method for tackling LP challenges.

The first improvement is presolving, simplifying the LP problem before solving by detecting inconsistent bounds, duplicate rows, and tightening bounds. This step reduces complexity and improves solver efficiency.

Next, preconditioning rescales variables and constraints within the LP instance to optimize numerical conditions and enhance convergence rates.

Infeasibility detection is another crucial aspect of PDLP. It allows for the identification of infeasible or unbounded problems without additional computational effort. This feature is rooted in the theory detailed in a SIAM Journal paper.

Adaptive restarts strategically decide when to optimally restart the PDHG algorithm to speed up convergence to high-accuracy solutions. Meanwhile, adaptive step-size selection dynamically adjusts the step size based on problem characteristics and algorithm performance, promoting faster convergence.

PDLP’s open-source nature, as part of Google’s OR-Tools, makes it easily accessible with Python, C++, Java, and C# interfaces. The solver is user-friendly, and detailed documentation provides examples for its application.

The impact of PDLP extends far beyond the realm of LP solvers. Its applications have already led to breakthroughs in various fields:

1. Data center network traffic engineering: PDLP enables efficient optimization of traffic routing across entire data center networks, saving significant machine resources.
2. Container shipping optimization: By solving the linear relaxation of massive integer two-layer multi-commodity flow problems, PDLP quantifies the quality of heuristics in this complex optimization problem.
3. Traveling salesman problem: PDLP has demonstrated its power by solving real-world TSP lower bound LP instances with up to 12 billion non-zero entries in the constraint matrix, surpassing even the most advanced commercial solvers.

The broader impacts of PDLP are equally impressive:

• cuPDLP.jl, an open-sourced GPU implementation of PDLP, has been developed.
• Commercial solver companies like Cardinal Optimizer and HiGHS have incorporated PDLP into their software.
• The academic community continues to explore and expand upon the theoretical foundations of PDLP, pushing the boundaries of what can be achieved in computational optimization.

As PDLP continues to evolve, its influence is expected to grow, bridging the gap between theoretical research and practical application. This revolutionary solver has the potential to transform the field of optimization, enabling solutions to previously intractable problems.