First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method

Please always quote using this URN: urn:nbn:de:0297-zib-74084
  • In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ambros GleixnerORCiD, Nils-Christian KempkeORCiD, Thorsten KochORCiD, Daniel RehfeldtORCiD, Svenja Uslu
Document Type:ZIB-Report
Tag:block structure; energy system models; high performance computing; interior-point method; linear programming; parallelization; preprocessing; presolving
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C05 Linear programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C06 Large-scale problems
Date of first Publication:2019/07/26
Series (Serial Number):ZIB-Report (19-39)
ISSN:1438-0064