P a PILO: A Parallel Presolving Library for Integer and Linear Optimization with Multiprecision Support

Ambros Gleixner (), Leona Gottwald () and Alexander Hoen ()
Additional contact information
Ambros Gleixner: Hochschule für Technik und Wirtschaft Berlin, 10318 Berlin, Germany; Zuse Institute Berlin, 14195 Berlin, Germany
Leona Gottwald: Zuse Institute Berlin, 14195 Berlin, Germany
Alexander Hoen: Zuse Institute Berlin, 14195 Berlin, Germany

INFORMS Journal on Computing, 2023, vol. 35, issue 6, 1329-1341

Abstract: Presolving has become an essential component of modern mixed integer program (MIP) solvers, both in terms of computational performance and numerical robustness. In this paper, we present P a PILO, a new C++ header-only library that provides a large set of presolving routines for MIP and linear programming problems from the literature. The creation of P a PILO was motivated by the current lack of (a) solver-independent implementations that (b) exploit parallel hardware and (c) support multiprecision arithmetic. Traditionally, presolving is designed to be fast. Whenever necessary, its low computational overhead is usually achieved by strict working limits. P a PILO’s parallelization framework aims at reducing the computational overhead also when presolving is executed more aggressively or is applied to large-scale problems. To rule out conflicts between parallel presolve reductions, P a PILO uses a transaction-based design. This helps to avoid both the memory-intensive allocation of multiple copies of the problem and special synchronization between presolvers. Additionally, the use of Intel’s Threading Building Blocks library aids P a PILO in efficiently exploiting recursive parallelism within expensive presolving routines, such as probing, dominated columns, or constraint sparsification. We provide an overview of P a PILO’s capabilities and insights into important design choices.

Keywords: presolving; parallel computing; mixed integer programming; linear programming; multi-precision computation (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0171 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:6:p:1329-1341

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().