PaPILO - Parallel Presolve for Integer and Linear Optimization
Leona Gottwald
Zuse Institute Berlin, Germany
Abstract:
Presolving is an essential part constributing to the performance of SCIP and other modern solvers. PaPILO, a new C++ library, provides presolving routines for MIP and LP problems. Many presolving steps for such problems can benefit greatly from having a global view on the constraint matrix. SCIP, however, is designed around constraint objects which contributes to its ability for handling a much larger class of problems than only MIPs. PaPILO is optimized for MIP and LP problems and complements SCIP in this regard as part of the newest release of the SCIP optimization suite.
Modern hardware requires parallel algorithms to utilize its full potential, yet even most commercial solvers do not use multi-threading for the preprocessing step as of today. While the presolving itself is designed to be fast despite the lack of parallelization, this can come at the cost of failing to find important reductions due to working limits and heuristic filtering. PaPILO's design facilitates use of parallel hardware to allow for more aggressive presolving and presolving of huge problems. The archtitecture of PaPILO allows presolvers generally to run in parallel without requiring expensive copies of the problem and without special synchronization in the presolvers themselves. Additionally, the use of Intel's TBB library aids PaPILO to efficiently exploit recursive parallelism within expensive presolving routines, such as probing, dominated columns, or constraint sparsification. Despite PaPILO's use of parallelization, its results are guaranteed to be deterministic independently of the number of threads available. This talk will give insights into the important design choices enabling PaPILO's capabilities and details of its parallel algorithms.