Distributed Parallel Structure-Aware Presolving for Arrowhead Linear Programs

Abstract

We present a structure-aware parallel presolve framework for arrowhead linear programs (AHLPs) in 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. Our presolve works on the distributed data of PIPS-IPM++, communicates only information on the linking parts of the problem, and preserves the arrowhead structure. Already on a single compute node with 64 processes, it outperforms PaPILO by a factor of 19 and Gurobi's presolve by a factor of 6 (shifted geometric mean), while removing a few percentage points fewer nonzeros. On large instances with small linking parts, multiple compute nodes make it 20 to 115 times faster than Gurobi's presolve. Presolve raises the number of instances solved by PIPS-IPM++ from 37 to 48. External presolve works with the modeler's annotation carried over, but it is slower, especially on large models, and breaks the distributed workflow. With automatic re-annotation, PIPS-IPM++ solves at most 21 instances.