Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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.
Metadaten
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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.