PIPS-IPM++ tools

pipstools is a collection of software tools that aims to give modellers easy access to the massively parallel solver PIPS-IPM++. The tools can be used to identify suitable block structures for linear optimisation problems, either based on domain information or in a fully automated manner using hypergraph partitioning. Furthermore, the identified block structures can be scored to estimate their expected performance with PIPS-IPM++, and can be visually inspected to help modellers improve the problem formulation.

Getting started

If you are using uv as your python package manager, annotation a problem file can be done with a single call:

uvx git+https://git@gitlab.com/pips-ipmpp/pipstools annotate problem.mps

For solving the problem with PIPS-IPM++ using e.g. a Docker imange please refer to the solver documentation.

Annotation

Problem annotation describes the process of identifying underlying block strucutres which the massivly parallel solver PIPS-IPM++ can exploit. Problem files can be provided either as .lp, .mps, or .gdx. If gurobipy is used as a file reader, also compressed files (.mps.gz, .lp.gz) can be provided. pipstools currently support two differnt modes of identifying block strucutres, user-defined annotations using domain knowledge and fully automated annotation using hypergraph partitioning.

Using variables names and regular expressions

Typcially, users are aware of the strucutre and interdependencies between variables and equation of their optimization problem. This can provide a good starting point by specifying variables naming patterns to be used for the decomposition. In the sample file of an energy system optimization model generated with the REMix framework the temporal dimension uses the naming pattern of tm followed by the integer of the specific timestep, e.g. tm1 to tm8760 for each timestep of a year. This specific pattern can be encoded as the regular expression "tm([0-9]+)" which captures the integer representing the timestep to maintain chronological ordering. Note, that using regular expressions for the annotation requires the problem file to include the actual variables as generated with the specific mathematical programming tool used.

pipstools annotate samples/remix.mps --regex-pattern=tm([0-9]+)

Using hypergraph partitioning

For problems without variable names or prior knowledge about the underlying problem strucutre, a fully automated annotation can be used. The algorithm first splits any dense variables (automatically detected by heuristics, can be changed using the --densecol argument), which in the case of energy system optimization problems typically corrosponds to investment decisions. The remaining problem strucute is then converted to a hypergraph using variables as nodes and constraints as hyperedges. Using the Karlsruhe Hypergraph Partitioner, a balanced partitioning into n partitions for the variables is generated (corresponding to the --blocks n argument). Afterwards, the constraints of the optimization problem are similarly paritioned taking into account the variable partions included in each constraint.

pipstools annotate samples/remix.mps --method hypergraph --blocks 30

Visualization

After the identification of block structures using the annotation functionality, the identified block structure can be explored visually using the included visulisation tool. By default it will try to plot the matrix using a matplot display and include both the annotation as well as variable and equation names. The matrix can be zoomed into, which further help refining the block structure and model formulation. If no display is available, the matrix plot can also be redirected to an image using the --output argument.

pipstools visualize samples/remix.gdx

Scoring of block strucutres

Scoring of the annotation is currently a work-in-progress feature.

Authors

• Manuel Wetzel (German Aerospace Center, DLR)
• Stephen Maher (GAMS Software GmbH)

Acknoledgements

pipstools was developed as a deliverable of the PEREGRINE project, which was funded by the German Federal Ministry for Economic Affairs and Energy under grant number 03EI1082A-B.