Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

PaPILO: A Parallel Presolving Library for Integer and Linear Programming with Multiprecision Support

epub ahead of print
  • 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 PaPILO, 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 PaPILO 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. PaPILO’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, PaPILO 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 PaPILO in efficiently exploiting recursive parallelism within expensive presolving routines, such as probing, dominated columns, or constraint sparsification. We provide an overview of PaPILO’s capabilities and insights into important design choices.
Metadaten
Author:Ambros GleixnerORCiD, Leona GottwaldORCiD, Alexander HoenORCiD
Document Type:Article
Parent Title (English):INFORMS Journal on Computing
Volume:35
Issue:6
First Page:1329
Last Page:1341
Year of first publication:2023
DOI:https://doi.org/10.1287/ijoc.2022.0171
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.