PaPILO — Parallel Presolve for Integer and Linear Optimization

PaPILO, a C++14-based software package, provides parallel presolve routines for (mixed integer) linear programming problems. The routines are implemented using templates which allows switching to higher precision or rational arithmetic using the boost multiprecision package.

PaPILO is part of the SCIP Optimization Suite, which is available under https://scipopt.org/.

PaPILO can be used as a header-based library and also provides an executable. Using the executable it is possible to presolve and postsolve MILP instances based on files. Additionally, PaPILO can be linked to SCIP, SoPlex, Gurobi, Glop, and HiGHS (https://github.com/ERGO-Code/HiGHS) solvers and act as a frontend. In this setting PaPILO passes the presolved problem to those solvers and applies the postsolve step to the optimal solution. When PaPILO is compiled as part of the SCIP Optimization Suite linking of SoPlex and SCIP solvers is performed automatically. Further, a Julia wrapper is available here.

Note: The original instance of this repository is hosted at git.zib.de and a read-only mirror is available at github.com/scipopt/papilo.

Dependencies

External dependencies that need to be installed by the user are the Intel TBB >= 2020, or TBB from oneAPI runtime library and boost >= 1.65 headers. The executable additionally requires some of the boost runtime libraries that are not required when PaPILO is used as a library. Under the folder external/ there are additional packages that are directly included within PaPILO and have a liberal open-source license.

If TBB is not found, then the current builds fails. The user has then the option to either enable the automatic download by adding -DTBB_DOWNLOAD to the cmake command or to disable it by adding -DTBB=off instead. However, it is strongly recommended to install an Intel TBB runtime library since it improves the runtime drastically.

We test PaPILO on some Debian, Ubuntu, macOS, and Windows system. While Papilo is likely to build and run on a wide variety of systems, compatibility is not guaranteed and support is limited.

Building

Building PaPILO works with the standard cmake workflow: (we recommend running the make command without specifying the number of jobs that can run simultaneously (no -j n), since this may cause large memory consumption and freeze of the machine)

mkdir build
cd build
cmake ..
make

Building PaPILO with SCIP, HiGHS, SoPlex or OrTools works also with the standard cmake workflow:

mkdir build
cd build
cmake -DSCIP_DIR=PATH_TO_SCIP_BUILD_DIR ..
make

After this, your PaPILO binary should be found in the bin folder. To install into your system, run sudo make install.

To install PaPILO into a folder, add -DCMAKE_INSTALL_PREFIX=/path/to/install/dir/ to the cmake call and run make install after the build.

If you use a relative path to SCIP, then the reference point is the location of the CMakeLists.txt. If you want to build PaPILO with a provided Boost version please specify its location: For CMake >= 3.30

-DBoost_DIR=PATH_TO_BOOST/lib/cmake/Boost-<BOOST_VERSION>

and for CMake < 3.30

-DBOOST_ROOT=PATH_TO_BOOST
-DBOOST_INCLUDEDIR=PATH_TO_BOOST/include

Solvers that are found in the system are automatically linked to the executable. Additionally one can specify the locations of solvers, e.g. with -DSCIP_DIR=<location of scip-config.cmake>, to allow PaPILO to find them in non-standard locations.

When tests are not necessary or fail to build, then use -DBUILD_TESTING=OFF to turn these off.

Usage of the binary

The PaPILO binary provides a list of all available functionality when the help flag -h or --help is specified. The binary provides the three subcommands solve, presolve, and postsolve. If no solvers are linked the solve subcommand will fail and print an error message.

Next we provide a small example of how the binary can be used to apply presolving and postsolving based on files.

Assuming a problem instance is stored in the file problem.mps the following call will apply presolving with standard settings and write the reduced problem to reduced.mps and all information that is needed for postsolve to the binary archive reduced.postsolve.

papilo presolve -f problem.mps -r reduced.mps -v reduced.postsolve

Not all presolver are able to dual-postsolve the dual solution (and the reduced costs and the basis information). Please use the settings file lp_presolvers_with_basis.set.

Now we can use the reduced problem reduced.mps to obtain a solution using any solver or from any other source to the file reduced.sol. The format of the solution should be one value per line given like this:

<variable name>        <value>

This is compatible with the solutions given on the MIPLIB 2017 homepage https://miplib.zib.de and with the solutions written by the SCIP solver. Variable names that are not found in the reduced problem are ignored.

The command for applying the postsolve step to the solution reduced.sol is then

papilo postsolve -v reduced.postsolve -u reduced.sol -l problem.sol

Giving the parameter -l problem.sol is optional and will store the solution transformed to the original space under problem.sol. The output of papilo contains some information about violations and objective value of the solution.

If PaPILO was linked to a suitable solver, then the above can also be achieved by using the solve subcommand like this:

papilo solve -f problem.mps -l problem.sol

This will presolve the problem, pass the reduced problem to a solver, and subsequently transform back the optimal solution returned by the solver and write it to problem.sol.

For the format of the solution and basis files please refer to Format.md

Using PaPILO as a library

PaPILO provides a templated C++ interface that allows to specify the type used for numerical computations. During configuration time PaPILO scans the system and provides the fastest available numeric types for quadprecision and for exact rational arithmetic in the file papilo/misc/MultiPrecision.hpp. Including this file will currently introduce the types

papilo::Quad
papilo::Float100
papilo::Float500
papilo::Float1000
papilo::Rational

The numeric type used by PaPILO will be referred to as REAL in the following section. It can be any of the above types as well as simply double for using standard double precision arithmetic.

To avoid confusion with types a short note on types like papilo:Vec and papilo::String. Those types are aliases for types from the standard library, std::vector and std::string, that possibly use an adjusted allocator. If nothing is altered regarding the allocator then the type papilo::Vec will be exactly the same as std::vector. It can be changed by adding a partial specialization of papilo::AllocatorTraits<T> after including papilo/misc/Alloc.hpp but before including any other header of PaPILO.

The C++ interface for using PaPILO mainly revolves around the classes

• papilo::Presolve<REAL>, which controls the presolving routines,
• papilo::Problem<REAL>, which holds the problem instance, and
• papilo::Postsolve<REAL>, which can transform solutions in the reduced space into solutions for the original problem space. The includes for those classes are under papilo/core/{Problem,Postsolve,Presolve}.hpp.

Creating an instance of papilo::Problem<REAL>

The PaPILO binary uses the MPS parsing routine to construct an instance of papilo::Problem<REAL> with the call papilo::MpsParser<REAL>::loadProblem("problem.mps").

For feeding a problem to PaPILO programmatically, there is the class papilo::ProblemBuilder<REAL>. This class allows to efficiently build an papilo::Problem<REAL> incrementally. The problem definition that PaPILO supports does not use a row sense, but uses left and right hand sides $l$ and $u$ of rows defined as $\text{l} \leq a^\top x \leq \text{u}$. For defining a row that is an equation with right hand side $b$ one has to set $l = u = b$. For inequalities either $l$ or $u$ are set to infinity. One thing where PaPILO differs from many solvers is how infinite values are encoded. Whether for column bounds or left/right hand sides of rows PaPILO encodes the infinite value as a logical condition. This ensures that regardless of numerical type used for REAL, that infinite values are always treated the same.

The member functions for initializing the rows and columns are

setNumCols( int ncols )
setNumRows( int nrows )

After calling those functions the problem will have no nonzero entries but the given number of columns and rows. The left and right hand side values of rows the rows are set to $0$ as well as the lower and upper bounds of the columns. Additionally all columns are initialized as continuous columns.

Next the following member functions can be used to alter the bound information about rows and columns as well as the objective coefficients and integrality flags of the columns.

• alter objective coefficient for columns

  setObj( int col, REAL val )
  

• alter bound information for columns

  setColLb( int col, REAL lb )
  setColLbInf( int col, bool isInfinite )
  setColUb( int col, REAL ub )
  setColUbInf( int col, bool isInfinite )
  

• mark column to be restricted to integral values or not

  setColIntegral( int col, bool isIntegral )
  

• alter left and right hand sides of rows

  setRowLhsInf( int row, bool isInfinite )
  setRowRhsInf( int row, bool isInfinite )
  setRowLhs( int row, REAL lhsval )
  setRowRhs( int row, REAL rhsval )
  

• set names of rows, columns, and the problem

  setRowName( int row, Str&& name )
  setColName( int col, Str&& name )
  setPro