Using a MIP Solver as a PDHG-Based MIP Heuristic
Abstract
The PDHG algorithm provides a new capability for solving difficult linear programming (LP) problems: the ability to find low-accuracy solutions quickly. While such solutions may not be applicable in all applications of LP, one possible use is to accelerate heuristics for finding feasible solutions to Mixed-Integer Programming (MIP) problems, where these approximate LP solutions can hopefully guide a heuristic towards accurate and high-quality MIP solutions. While a monolithic heuristic that exploits PDHG solutions would be useful, we pose a broader question here: could we replace the default LP solver in a modern MIP solver with PDHG to accelerate most (or all) of its existing heuristics? We find that doing so does have some obvious drawbacks, preventing us from using several powerful MIP techniques, but it leaves most others unaffected, ultimately resulting in a heuristic that often finds high-quality, high-accuracy solutions faster than current state-of-the-art strategies.
Related
- cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
- Inexact PDHG for Large-Scale Semidefinite Programming
- A Triangular Log-Det PDHG for Semidefinite Programming: Complementarity Selection and Global Linear Convergence
- H-PDLP: GPU-Accelerated Linear Programming via Generalized PDHG and Homogeneous Self-Dual Embedding
- Level-Set Geometry and the Theoretical Performance of PDHG for Conic Linear Optimization
BibTeX
@misc{rothberg2026using,
title = {{Using a MIP Solver as a PDHG-Based MIP Heuristic}},
author = {Edward Rothberg},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.14483},
eprint = {2607.14483},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.14483},
}
RIS
TY - UNPB
TI - Using a MIP Solver as a PDHG-Based MIP Heuristic
AU - Edward Rothberg
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2607.14483
UR - https://arxiv.org/abs/2607.14483
AB - The PDHG algorithm provides a new capability for solving difficult linear programming (LP) problems: the ability to find low-accuracy solutions quickly. While such solutions may not be applicable in all applications of LP, one possible use is to accelerate heuristics for finding feasible solutions to Mixed-Integer Programming (MIP) problems, where these approximate LP solutions can hopefully guide a heuristic towards accurate and high-quality MIP solutions. While a monolithic heuristic that exploits PDHG solutions would be useful, we pose a broader question here: could we replace the default LP solver in a modern MIP solver with PDHG to accelerate most (or all) of its existing heuristics? We find that doing so does have some obvious drawbacks, preventing us from using several powerful MIP techniques, but it leaves most others unaffected, ultimately resulting in a heuristic that often finds high-quality, high-accuracy solutions faster than current state-of-the-art strategies.
ER -