Metraipolis › archive › dc_a16ca6962fbb
Reformulation Techniques for PDLP with Applications to QUBO and Joint Replenishment — arXiv:2611.05076
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05076
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T18:59:38.413Z
- SHA-256 of the archived text
654daa1f5b29b6378f97b335bffd304c00d44efd18314823fdcb396c15f51403- Stable URL of this page
https://metraipolis.com/documento/dc_a16ca6962fbb
How to cite
Reformulation Techniques for PDLP with Applications to QUBO and Joint Replenishment — arXiv:2611.05076 — arXiv (en), https://arxiv.org/abs/2611.05076 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a16ca6962fbb (Metraipolis archive dc_a16ca6962fbb, sha256 654daa1f5b29b6378f97b335bffd304c00d44efd18314823fdcb396c15f51403)
BibTeX
@misc{dca16ca6962fbb,
title = {Reformulation Techniques for PDLP with Applications to QUBO and Joint Replenishment — arXiv:2611.05076},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05076},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a16ca6962fbb; sha256 654daa1f5b29b6378f97b335bffd304c00d44efd18314823fdcb396c15f51403},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05076. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno). Categorie arXiv: Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2611.05076 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-04T18:37:22.162Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).