TY - GEN A1 - Kempke, Nils-Christian A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - A Massively Parallel Interior-Point-Method for Arrowhead Linear Programs N2 - In practice, non-specialized interior point algorithms often cannot utilize the massively parallel compute resources offered by modern many- and multi-core compute platforms. However, efficient distributed solution techniques are required, especially for large-scale linear programs. This article describes a new decomposition technique for systems of linear equations implemented in the parallel interior-point solver PIPS-IPM++. The algorithm exploits a matrix structure commonly found in optimization problems: a doubly-bordered block-diagonal or arrowhead structure. This structure is preserved in the linear KKT systems solved during each iteration of the interior-point method. We present a hierarchical Schur complement decomposition that distributes and solves the linear optimization problem; it is designed for high-performance architectures and scales well with the availability of additional computing resources. The decomposition approach uses the border constraints’ locality to decouple the factorization process. Our approach is motivated by large-scale unit-commitment problems. We demonstrate the performance of our method on a set of mid-to large-scale instances, some of which have more than 10^9 nonzeros in their constraint matrix. T3 - ZIB-Report - 24-13 KW - direct methods for linear systems KW - mathematical programming KW - parallel computation KW - linear programming KW - large-scale problems KW - interior-point methods Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-98829 SN - 1438-0064 ER - TY - GEN A1 - Kempke, Nils-Christian A1 - Maher, Stephen John A1 - Rehfeldt, Daniel A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Uslu, Svenja T1 - Distributed Parallel Structure-Aware Presolving for Arrowhead Linear Programs N2 - 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. T3 - ZIB-Report - 26-01 KW - Linear Programming KW - Presolving KW - Large-Scale Optimization KW - Distributed Parallel Computing KW - Arrowhead Y1 - 2026 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-103034 SN - 1438-0064 ER -