Optimization Online


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

Ambros Gleixner (gleixner***at***zib.de)
Nils-Christian Kempke (kempke***at***zib.de)
Thorsten Koch (koch***at***zib.de)
Daniel Rehfeldt (rehfeldt***at***zib.de)
Svenja Uslu (uslu***at***zib.de)

Abstract: 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.

Keywords: block structure; energy system models; high performance computing; interior-point method; linear programming; parallelization; preprocessing; presolving

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: ZR-19-39, Zuse Institute Berlin, Takustr. 7, 14195 Berlin, 07/2019

Download: [PDF]

Entry Submitted: 07/26/2019
Entry Accepted: 07/26/2019
Entry Last Modified: 08/02/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society