PaperlayerView exact revision on arXiv

Source-linked AI summary

Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient

David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O'Donoghue, Warren Schudy

arXiv:2106.04756v2math.OC

TL;DR

First-order methods can struggle to reach the high precision required in linear programming, despite LP solvers being mature and reliable. PDLP applies PDHG to an LP saddle-point formulation and adds practical enhancements, obtaining high-quality solutions and solving 283 of 383 problems under the reported conditions. The results provide evidence that first-order methods can be useful beyond moderately accurate solutions, while PDLP remains a component for a broader solver portfolio rather than a complete replacement.

  • Problem

    First-order methods often slow substantially as they approach optimality, whereas traditional linear-programming applications may require high precision.

  • Method

    PDLP applies primal-dual hybrid gradient to a saddle-point formulation of linear programming and combines adaptive restarting, dynamic step sizes, presolving, and diagonal preconditioning.

  • Results

    PDLP solves 283 of 383 problems under the reported relative-accuracy and iteration-limit conditions and is competitive with a commercial LP solver in a small number of cases.

  • Takeaways & Limitations

    The experiments provide evidence that first-order methods can obtain high-quality LP solutions and are not useful only when moderate accuracy is desired.

  • Takeaways & Limitations

    The complete PDLP algorithm has no convergence guarantee, and the results do not establish that it matches the full portfolio of methods offered by a commercial solver.

Abstract

from arXiv · show

We present PDLP, a practical first-order method for linear programming (LP) that can solve to the high levels of accuracy that are expected in traditional LP applications. In addition, it can scale to very large problems because its core operation is matrix-vector multiplications. PDLP is derived by applying the primal-dual hybrid gradient (PDHG) method, popularized by Chambolle and Pock (2011), to a saddle-point formulation of LP. PDLP enhances PDHG for LP by combining several new techniques with older tricks from the literature; the enhancements include diagonal preconditioning, presolving, adaptive step sizes, and adaptive restarting. PDLP improves the state of the art for first-order methods applied to LP. We compare PDLP with SCS, an ADMM-based solver, on a set of 383 LP instances derived from MIPLIB 2017. With a target of $10^{-8}$ relative accuracy and 1 hour time limit, PDLP achieves a 6.3x reduction in the geometric mean of solve times and a 4.6x reduction in the number of instances unsolved (from 227 to 49). Furthermore, we highlight standard benchmark instances and a large-scale application (PageRank) where our open-source prototype of PDLP, written in Julia, outperforms a commercial LP solver.

1 Introduction

The paper argues that enhanced first-order methods can deliver highly accurate LP solutions while addressing the scalability limits of traditional methods. It introduces PDLP and reports substantially stronger performance than baseline first-order approaches on standard benchmarks.

  • LP applications demand higher precision than the moderately accurate solutions often sufficient for large machine-learning workloads.First-order methods can suffer tailing off as they approach optimality.
  • The work addresses a gap between first-order algorithms described in the literature and the practical techniques needed for strong LP performance.The authors emphasize comprehensive computational testing of combined enhancements.
  • PDLP combines PDHG with adaptive restarting, dynamic step sizes, presolving, and diagonal preconditioning for LP.The method applies PDHG to a saddle-point formulation and combines theoretical enhancements with practical heuristics.
  • 283 of 383 MIPLIB 2017 LP instances reached 10^-8 relative accuracy with PDLP, versus 50 for baseline PDHG.Both results use approximately 100,000 iterations per problem.
  • PDHG is matrix-free, using matrix-vector multiplications that support very large-scale and parallel computation.The paper identifies potential execution on multithreaded CPUs, GPUs, and distributed clusters.

2 Preliminaries

The paper formulates LP as a primal-dual saddle-point problem and applies PDHG through projected primal and dual updates. Its notation defines feasible sets, step-size parameters, and the primal-weight reparameterization used to control iterate scaling.

  • The primal-dual LP formulation is equivalent to a saddle-point problem over bounded primal variables and sign-constrained dual variables.The feasible sets are X := {x ∈ R^n : l ≤ x ≤ u} and Y := {y ∈ R^(m1+m2) : y_1:m1 ≥ 0}.
  • PDHG updates primal and dual iterates by projecting gradient-like steps onto X and Y.The algorithm is introduced as the specialization of PDHG to the LP saddle-point formulation.
  • τ and σ are the primal and dual step sizes, while η and ω reparameterize them as τ = η/ω and σ = ωη.ω is the primal weight and η is the step size.
  • Under the reparameterization, PDHG converges for η ≤ 1/∥K∥2 while ω controls the scaling between primal and dual iterates.The primal weight corresponds to weighting primal variables in the norm used in PDHG theory.
  • The baseline comparison uses η = 0.9/∥K∥2, with ∥K∥2 estimated by power iteration, and sets ω = 1.These choices are similar to default parameters in a standard PDHG implementation.

3 Practical algorithmic improvements

PDLP combines adaptive step sizes, restarts, primal-weight updates, presolving, and diagonal preconditioning to improve practical PDHG performance for LP. The full algorithm prioritizes practical performance, although it lacks an overall convergence guarantee.

  • Theoretical guarantees: The complete PDLP algorithm has no convergence guarantee, although restart criteria, presolve, and diagonal preconditioning preserve theoretical guarantees individually.The adaptive step-size rule lacks a convergence proof, while convergence for primal-weight updates is conjectured under infrequent updates.
  • PDLP combines adaptive step sizes, adaptive restarting, dynamic primal-weight updates, presolving, and diagonal preconditioning around a baseline PDHG method.The algorithm applies presolve and diagonal preconditioning before its iterative updates, which include modified step sizes, restarts, and primal-weight updates.
  • Adaptive step sizes: Adaptive step sizes adjust η dynamically, reducing and retrying a step when the convergence condition is not satisfied.This avoids relying solely on a pessimistic fixed step size based on an estimated spectral norm.
  • Adaptive restarting: Adaptive restarts use normalized duality-gap criteria to select restart candidates and detect sufficient decay, insufficient progress, or overly long inner loops.The normalized duality gap is finite, computable in linear time, and zero exactly at an optimal solution.
  • Primal-weight updates: The primal-weight heuristic seeks to balance primal and dual distances, smooths updates on a log scale, and yields scale-invariant behavior in a simplified setting.The paper notes that primal-weight updates occur during restarts and may change substantially without the instability associated with frequent large updates.
  • Presolving and diagonal preconditioning: Presolving simplifies LP inputs through transformations such as removing empty rows or fixed variables, while diagonal preconditioning rescales matrix rows and columns to improve balance.Both techniques can be interpreted as applying PDHG to an LP instance with transformed data; presolve is evaluated experimentally using PaPILO.

4 Numerical experiments

The experiments evaluate PDLP on multiple LP benchmarks against first-order baselines and commercial LP methods, including large-scale PageRank instances. They examine enhancement effects, termination criteria, and performance under fixed KKT-pass or time limits.

  • 4.1 Experimental setup: PDLP is evaluated on MIP Relaxations, LP benchmark, and Netlib datasets, with comparisons against SCS, enhanced extragradient, and Gurobi.The MIP Relaxations set contains 383 instances, while the LP benchmark contains 56 problems; Netlib provides an additional historical benchmark.
  • 4.1 Experimental setup: The experiments use 100,000 KKT passes for enhancement studies and a 1-hour limit for first-order baseline comparisons.KKT passes count matrix multiplications by K and K^T, providing a less noisy metric than runtime for matrix-free solvers.
  • 4.2 Impact of PDLP’s improvements: Each modification improves baseline PDHG on normalized KKT-pass performance except presolve on LP benchmark at tolerance 10^-4.Figure 1 reports shifted geometric means of KKT passes normalized by baseline PDHG.
  • 4.4 PDLP versus simplex and barrier: PDLP is compared with Gurobi’s barrier, primal simplex, and dual simplex methods at 10^-8 termination accuracy, with Gurobi outperforming PDLP on most instances.Some instances nevertheless show moderate to significant gains for PDLP.
  • 4.5 PageRank: The PageRank experiments use large instances from preferential-attachment graphs to compare PDLP, SCS, and Gurobi methods.The LP formulation is used as a source of very large instances rather than as the best method for computing PageRank.

5 Conclusions and future work

The authors find the experiments encouraging for applying first-order methods to LP and argue that the results motivate further theoretical and computational investigation. They envision PDLP or related approaches becoming part of the standard LP toolkit after additional refinements.

  • 5 Conclusions and future work: The experiments provide evidence against the claim that first-order methods are useful only when moderately accurate solutions are desired.The authors also identify open questions about instance difficulty and transformations that could accelerate solving.
  • 5 Conclusions and future work: The authors hope released benchmarks and baselines will support further investigation of first-order methods for LP.They specifically connect practical heuristic success with motivation for additional theoretical study.

A Proof of scale invariance of primal weight initialization scheme

This appendix proves that the primal weight initialization scheme is invariant under the specified scaling of the LP data and initial iterates. The proof proceeds by induction over PDHG iterations.

  • A Proof of scale invariance of primal weight initialization scheme: Under the stated positive scalings of K, c, q, l, u, and initial iterates, the scaled PDHG iterates satisfy x_hat_k = alpha_x x_k and y_hat_k = alpha_y y_k.The proposition states this relation for every k in {0} union N, and the proof begins with the base case k = 0.

B MIP Relaxations dataset

The MIP Relaxations dataset contains 383 LP instances derived from selected MIPLIB 2017 problems, with size and feasibility-related filters. The appendix also reports ablation-study settings and step-size performance materials for this dataset.

  • B MIP Relaxations dataset: The selected dataset excludes smaller instances and extends beyond the MIPLIB benchmark’s 1,000,000-nonzero limit for experimental convenience.The resulting collection emphasizes larger LP relaxations than the benchmark subset.
  • B MIP Relaxations dataset: The ablation study disables each PDLP enhancement separately and evaluates alternatives using 100,000 KKT passes and a 6-hour limit.Unsolved instances are assigned 100,000 KKT passes and 6 hours.

C.1 Step size choice

The step-size ablation compares fixed and Malitsky–Pock policies, finding that PDLP performs slightly better than tuned alternatives and nearly matches per-instance tuning at high accuracy.

  • C.1 Step size choice: The ablation compares fixed step size, best fixed Malitsky–Pock tuning, and best per-instance Malitsky–Pock tuning.The per-instance variant is a virtual solver combining 42 hyperparameter configurations.
  • C.1 Step size choice: PDLP is slightly better than tuned Malitsky–Pock and nearly matches per-instance tuning at high accuracy.The comparison uses Figures 3 and Tables 3 and 4.
  • C.1 Step size choice: The best configuration uses downscaling factor = 0.5 and interpolation coefficient = 0.4 at both 10^-4 and 10^-8 accuracy.

C.3 Primal weight updates

Primal-weight experiments show that PDLP’s adaptive updates outperform fixed-weight alternatives at high accuracy, while presolve and diagonal preconditioning further improve performance.

  • C.3 Primal weight updates: The single best fixed primal-weight bias is ξ = 0.1 at both 10^-4 and 10^-8 accuracy, with ξ = 1 performing similarly.
  • C.3 Primal weight updates: PDLP outperforms the best per-instance fixed primal weight at high accuracy and is competitive at low accuracy.The comparison is reported for the primal-weight ablation.
  • C.3 Primal weight updates: Presolve reduces solve time more than KKT passes because it also makes each KKT pass faster by shrinking the problem.
  • C.5 Diagonal preconditioning: The combined Ruiz and Pock-Chambolle preconditioner significantly outperforms no scaling and either individual baseline.The separation is also visible in solved-instance counts as a function of KKT passes.

E Additional PDLP improvements results

The appendix reports tabular performance statistics for PDLP improvements and baselines across LP Benchmark, Netlib, and MIP Relaxations datasets at two accuracy tolerances.

  • LP Benchmark and Netlib: Tables 15–18 report PDLP improvement statistics for the LP Benchmark and Netlib datasets at 10^-4 and 10^-8 tolerances.Tables 15–16 cover LP Benchmark, while Tables 17–18 cover Netlib.
  • MIP Relaxations: Tables 17–18 report baseline performance statistics for MIP Relaxations at 10^-4 and 10^-8 tolerances.
  • Baseline comparisons: Tables 19–24 report baseline performance statistics for LP Benchmark and Netlib at 10^-4 and 10^-8 tolerances.Tables 19–20 cover LP Benchmark, and Tables 21–22 cover Netlib.

F Additional baseline comparison results

The supplementary material documents commands and settings for reproducing baseline, ablation, and solver-comparison experiments, including SCS, PDLP, and Gurobi.

  • F Additional baseline comparison results: The full experiment suite requires approximately 12,500 CPU-hours and therefore a cluster or cloud computing environment.
  • F Additional baseline comparison results: SCS can run in matrix-free mode or use a cached LDL factorization for its per-iteration linear system.
  • F Additional baseline comparison results: The appendix gives command-line settings for step-size, restart, primal-weight, presolve, and diagonal-preconditioning ablations.

G.3 Improvements experiment

The improvements experiment documents the configurations used to compare baseline PDHG with progressively enhanced variants, culminating in PDLP on a presolved dataset.

  • G.3 Improvements experiment: Each run uses a common invocation with a selected tolerance, shared restart metric, iteration limit, and method setting.The common settings include a 100,000 KKT matrix-pass limit and gap-over-distance restarting metric.
  • G.3 Improvements experiment: The documented example runs the scaling configuration with relative and absolute optimality tolerances of 10^-4.The command uses constant step size and disables scale-invariant initial primal weighting.
  • G.3 Improvements experiment: The ablation study compares baseline PDHG with configurations that successively add scaling, restarting, step-size selection, and presolve.The baseline runs on the original dataset, while the final PDLP configuration switches to presolved data.
  • G.3 Improvements experiment: The ablation-study command invokes the PDHG method with relative and absolute tolerances supplied through the experiment configuration.The command also uses the gap-over-distance restart metric and operates on the presolved MIP Relaxations dataset.
Loading 2106.04756v2…