Fix-and-Propagate Heuristics Using Low-Precision First-Order LP Solutions for Large-Scale Mixed-Integer Linear Optimization
accepted for publication
- We investigate the use of low-precision first-order methods (FOMs) within a fix-and-propagate (FP) framework for solving mixed-integer programming problems (MIPs). We employ GPU-accelerated PDLP, a variant of the Primal-Dual Hybrid Gradient (PDHG) method specialized to LP problems, to solve the LP-relaxation of our MIPs to low accuracy. This solution is used to motivate fixings within our FP framework. We evaluate the performance of our heuristic on MIPLIB 2017, demonstrating that low-accuracy LP solutions do not lead to a loss in the quality of the FP heuristic solutions. Further, we use our FP framework to produce high-accuracy solutions for large-scale (up to 243 million nonzeros and 8 million decision variables) unit commitment-based dispatch and expansion planning problems created with the modeling framework REMix. For the largest problems, we can generate solutions with a primal-dual gap of under 2% in less than 4 hours, whereas state-of-the-art commercial solvers cannot produce feasible solutions within 2 days of runtime.
| Author: | Nils-Christian KempkeORCiD, Thorsten KochORCiD |
|---|---|
| Document Type: | Article |
| Parent Title (English): | Mathematical Programming Computation |
| Tag: | Integer programming; Large scale optimization; Linear Programming; OR in energy; Primal heuristics |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
| Year of first publication: | 2026 |
| ArXiv Id: | http://arxiv.org/abs/2503.10344 |
| Preprint: | urn:nbn:de:0297-zib-99612 |
| DOI: | https://doi.org/10.1007/s12532-026-00312-7 |

