PIPS-IPM++ Solver and Tools
a parallel interior-point method for doubly bordered block diagonal linear programs
PIPS-IPM++ Solver and Tools

PIPS-IPM++ is a parallel interior-point solver for doubly bordered block diagonal Linear Programs. It is available as open-source from https://gitlab.com/pips-ipmpp/pips-ipmpp.

Mathematically, PIPS-IPM++ works on LPs in block-diagonal structure with both linking constraints and linking variables:

\begin{align}\text{min} \quad & c_0^T x_0 & + & c_1^T x_1 & + & c_2^T x_2 & \cdots\; & + c_N^T x_N \\ \text{s.t.} \quad & T_0 x_0 & & && & & & =\; & h_0 \\ & T_1 x_0 & + & W_1 x_1 && & & & =\; & h_1 \\ & T_2 x_0 & & & + & W_2 x_2 & & & =\; & h_2 \tag{BlockLP} \\ & \vdots & & && & \ddots\; & & & \vdots \\ & T_N x_0 & & && & & + W_N x_N & =\; & h_N \\ & F_0 x_0 & + & F_1 x_1 & + & F_2 x_2 & \cdots\; & + F_N x_N & =\; & h_{N+1}, \end{align}

with \(x = (x_0, x_1,...,x_N)\). The linking variables are represented by the vector \(x_0\), whereas the linking constraints are described by the matrices \(F_0,\ldots,F_N\), and the vector \(h_{N+1}\).

A pivotal ingredient of PIPS-IPM++ is the parallelization (via Message Passing Interface (MPI)) of the linear system that has to be solved in each iteration of its interior point algorithm. This parallelization further allows that the whole LP can be distributed among the MPI-processes, with no process needing to store the entire problem. For more information on the algorithms implemented by PIPS-IPM++, see PIPS-IPM++ Algorithm.

PIPS-IPM++ is a (highly modified) derivative of the PIPS-IPM solver originally developed at Argonne National Laboratory. PIPS-IPM is derivative work of OOQP by E. Michael Gertz and Stephen Wright. While the original code retains its old licensing, all PIPS-IPM++ additions are distributed under the LGPLv3. See also the LICENSE file. A list of PIPS-IPM++ authors and contributors is available at Authors and Acknowledgements.

Getting Started

To get started quickly, the use of a Docker image with prebuilt PIPS-IPM++ is suitable. See The PIPS-IPM++ Docker Image on how to use this image. With the Docker image, all cores of a single machine can be utilized to solve an LP by PIPS-IPM++.

More experienced used, or users that want to distribute their LP solve on a HPC cluster, may want to compile PIPS-IPM++ from source. Compilation instructions are available at Compiling PIPS-IPM++.

Currently, there exists only one maintained interface to PIPS-IPM++, which uses GAMS Data Exchange (GDX) files for input. Such GDX files contain the data of the LP (BlockLP) including the block-decomposition. How to generate such a GDX file is described in PIPS-IPM++ Input: Format and Generation.

For more information on how to run the PIPS-IPM++ executable and available options, see Running PIPS-IPM++.

References (bib)