@misc{KempkeKoch2025, author = {Kempke, Nils-Christian and Koch, Thorsten}, title = {Low-precision first-order method-based fix-and-propagate heuristics for large-scale mixed-integer linear optimization}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2503.10344}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99612}, year = {2025}, abstract = {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). FOMs, using only matrix-vector products instead of matrix factorizations, are well suited for GPU acceleration and have recently gained more attention for their application to large-scale linear programming problems (LPs). We employ 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 fix-and-propagate framework. We implemented four different FP variants using primal and dual LP solution information. We evaluate the performance of our heuristics on MIPLIB 2017, showcasing that the low-accuracy LP solution produced by the FOM does not lead to a loss in quality of the FP heuristic solutions when compared to a high-accuracy interior-point method LP solution. Further, we use our FP framework to produce high-accuracy solutions for large-scale (up to 243 million non-zeros and 8 million decision variables) unit-commitment energy-system optimization models created with the modeling framework REMix. For the largest problems, we can generate solutions with under 2\% primal-dual gap in less than 4 hours, whereas commercial solvers cannot generate feasible solutions within two days of runtime. This study represents the first successful application of FOMs in large-scale mixed-integer optimization, demonstrating their efficacy and establishing a foundation for future research in this domain.}, language = {en} } @misc{KempkeMaherRehfeldtetal.2026, author = {Kempke, Nils-Christian and Maher, Stephen John and Rehfeldt, Daniel and Gleixner, Ambros and Koch, Thorsten and Uslu, Svenja}, title = {Distributed Parallel Structure-Aware Presolving for Arrowhead Linear Programs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-103034}, year = {2026}, abstract = {We present a structure-aware parallel presolve framework specialized to arrowhead linear programs (AHLPs) and designed for high-performance computing (HPC) environments, integrated into the parallel interior point solver PIPS-IPM++. Large-scale LPs arising from automated model generation frequently contain redundancies and numerical pathologies that necessitate effective presolve, yet existing presolve techniques are primarily serial or structure-agnostic and can become time-consuming in parallel solution workflows. Within PIPS-IPM++, AHLPs are stored in distributed memory, and our presolve builds on this to apply a highly parallel, distributed presolve across compute nodes while keeping communication overhead low and preserving the underlying arrowhead structure. We demonstrate the scalability and effectiveness of our approach on a diverse set of AHLPs and compare it against state-of-the-art presolve implementations, including PaPILO and the presolve implemented within Gurobi. Even on a single machine, our presolve significantly outperforms PaPILO by a factor of 18 and Gurobi's presolve by a factor of 6 in terms of shifted geometric mean runtime, while reducing the problems by a similar amount to PaPILO. Using a distributed compute environment, we outperform Gurobi's presolve by a factor of 13.}, language = {en} }