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

Distributed Parallel Structure-Aware Presolving for Arrowhead Linear Programs

Please always quote using this URN: urn:nbn:de:0297-zib-103034
  • 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.

Download full text files

Export metadata

Metadaten
Author:Nils-Christian KempkeORCiD, Stephen John MaherORCiD, Daniel RehfeldtORCiD, Ambros GleixnerORCiD, Thorsten KochORCiD, Svenja Uslu
Document Type:ZIB-Report
Tag:Arrowhead; Distributed Parallel Computing; Large-Scale Optimization; Linear Programming; Presolving
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Date of first Publication:2026/03/03
Series (Serial Number):ZIB-Report (26-01)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.