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 with a 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}, \\ & x_0, & & x_1, & & x_2, & \ldots\; & x_N & \geq & 0, \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}\). The actual implementation allows also ranged and inequality constraints and arbitrary variable bounds.

This structure is common in many areas, including stochastic programming, decomposition methods, and multi-period planning problems. In the context of energy system planning applications,

  • the linking variables \(x_0\) represent global strategic decisions that are imposed over many time periods,
  • each block \(i=1, \dots, N\) corresponds to a time-period or stage,
  • the matrices \(T_i\) (couple the global decisions to the time-period decisions) and \(F_i\) (couple the time-period decision) define the linkage between stages, and
  • the matrices \(W_i\) define the constraints within each time-period.

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 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 Docker image with prebuilt PIPS-IPM++ is suitable. With the Docker image, all cores of a single machine can be utilized to solve an LP by PIPS-IPM++.

The behavior of PIPS-IPM++ can be influenced by setting various Solver Options.

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 Compilation.

An existing interface to PIPS-IPM++ uses GAMS Data Exchange (GDX) files as input. Such GDX files contain the data of the LP (BlockLP) including the block-decomposition. How to generate such a GDX file and run the corresponding executables is described in Running on GDX input.

Developers of new interfaces may be interested in the C++ API Overview and C API Overview.

References (bib)