Reformulation Techniques for PDLP with Applications to QUBO and Joint Replenishment
Abstract
Practitioners of linear programming widely believe that reformulating a linear program (LP) offers little benefit to interior-point methods: their iteration counts are famously insensitive to the formulation, so the payoff of reformulation beyond automatic presolve and customized linear solve is modest. This paper presents evidence that the same is not true of first-order solvers built on the primal-dual hybrid gradient method (PDHG), such as PDLP. Unlike interior-point methods, PDHG-type methods have per-iteration costs governed by the matrix representation of the formulation and iteration counts governed by its geometry, and both change under equivalent reformulations. We describe a general reformulation recipe: constraints drawn from a catalogue of projection-friendly polyhedra can be absorbed into the projection step of PDHG. We analyze what absorption does to the four constants that govern restarted PDHG: the coupling norm, the termination certificate, the distance scale, and the sharpness modulus. We perform the reformulation on two case studies. On the LP relaxation of quadratic unconstrained binary optimization (QUBO), absorption makes any step size below $1$ admissible on every instance, and yields a fully explicit linear rate. On the LP relaxation of the joint replenishment problem (JRP), whose optimum certifies a $2$-approximation for an NP-hard inventory problem, absorption improves the coupling norm and eliminates every matrix-vector product. Both reformulations run on GPUs with custom kernels in place of sparse matrix-vector products. We benchmark both against the GPU LP solver cuPDLPx applied to the original formulations. By solve time, the reformulated solvers are $6.4−9.6\times$ faster on QUBO and $6.1−28.9\times$ faster on the JRP. They take $1.7−4.3\times$ and $13.6−52.3\times$ fewer iterations respectively.
Related
- H-PDLP: GPU-Accelerated Linear Programming via Generalized PDHG and Homogeneous Self-Dual Embedding
- Hidden Convexity of the Joint Range of Three Quadratic Forms and Applications
- Polar Complexity: A New Descriptive Complexity with Applications to Source and Joint Source-Channel Coding
- Open-Loop Stackelberg LQ Difference Games with Coupled-Affine Inequality Constraints: An Exact OCP--LCS/LCQP Reformulation
- M-Eigenpairs of Partially Symmetric Tensors: Exact Reformulation and Perturbation Bounds
BibTeX
@misc{dentes2026reformulation,
title = {{Reformulation Techniques for PDLP with Applications to QUBO and Joint Replenishment}},
author = {Jacob Dentes and Haihao Lu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05076},
eprint = {2611.05076},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05076},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Reformulation Techniques for PDLP with Applications to QUBO and Joint Replenishment
AU - Jacob Dentes
AU - Haihao Lu
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05076
UR - https://arxiv.org/abs/2611.05076
AB - Practitioners of linear programming widely believe that reformulating a linear program (LP) offers little benefit to interior-point methods: their iteration counts are famously insensitive to the formulation, so the payoff of reformulation beyond automatic presolve and customized linear solve is modest. This paper presents evidence that the same is not true of first-order solvers built on the primal-dual hybrid gradient method (PDHG), such as PDLP. Unlike interior-point methods, PDHG-type methods have per-iteration costs governed by the matrix representation of the formulation and iteration counts governed by its geometry, and both change under equivalent reformulations. We describe a general reformulation recipe: constraints drawn from a catalogue of projection-friendly polyhedra can be absorbed into the projection step of PDHG. We analyze what absorption does to the four constants that govern restarted PDHG: the coupling norm, the termination certificate, the distance scale, and the sharpness modulus. We perform the reformulation on two case studies. On the LP relaxation of quadratic unconstrained binary optimization (QUBO), absorption makes any step size below $1$ admissible on every instance, and yields a fully explicit linear rate. On the LP relaxation of the joint replenishment problem (JRP), whose optimum certifies a $2$-approximation for an NP-hard inventory problem, absorption improves the coupling norm and eliminates every matrix-vector product. Both reformulations run on GPUs with custom kernels in place of sparse matrix-vector products. We benchmark both against the GPU LP solver cuPDLPx applied to the original formulations. By solve time, the reformulated solvers are $6.4−9.6\times$ faster on QUBO and $6.1−28.9\times$ faster on the JRP. They take $1.7−4.3\times$ and $13.6−52.3\times$ fewer iterations respectively.
ER -