As operations research practitioners, we understand that presolving has become indispensable for modern optimization solvers. Until recently, however, the field lacked a comprehensive, solver-independent solution that could harness parallel computing and multiprecision arithmetic.
PaPILO is a C++ header-only library offering an extensive collection of presolving routines for mixed-integer and linear programming problems. It stands out due to its sophisticated architecture and practical versatility.
The library's transaction-based design prevents conflicts during parallel reductions, a critical innovation for concurrent presolving operations. PaPILO effectively utilizes recursive parallelism in computationally demanding routines using Intel's TBB library.
The template-based implementation allows for smooth transitions between precision levels, ranging from standard double precision to quad precision and exact rational arithmetic. This flexibility is essential for numerically challenging instances in which standard floating-point arithmetic could compromise the quality of the solution.
PaPILO implements presolving techniques that operate at different levels of complexity:
- Fast methods that examine individual constraints or variables.
- Medium-complexity approaches for row and column analysis.
- Exhaustive techniques that provide comprehensive problem reduction. The parallelization framework mitigates the computational overhead that has traditionally limited the application of aggressive presolving to large-scale problems.
The benchmark results demonstrate impressive scalability. Instances requiring over 100 seconds achieve a 7.0x speedup with 32 threads compared to single-threaded execution. The framework can function as either a standalone preprocessing tool or an integrated component.
For the optimization community, PaPILO is more than just a technical advancement. It is a production-ready tool that provides access to sophisticated presolving capabilities and addresses the parallel computing paradigm that defines modern high-performance computing.
PaPILO is available as open source under the Apache 2.0 license and is part of the SCIP Optimization Suite. It merits consideration for any serious mixed integer programming implementation.
- PaPILO, GitHub repo
- "PaPILO: A Parallel Presolving Library for Integer and Linear Programming with Multiprecision Support", arXiv, Mar 2024
- The fractal image was created using the JavaScript Fractal Explorer program, which was written by James Wilson.
#OperationsResearch
#Optimization
#MixedIntegerProgramming
#ParallelComputing
#SCIP
#OpenSource
