GraphILP

GraphILP is a Python API to automatically cast graph-related optimisation problems into integer linear programming (ILP) instances.

• Source: https://github.com/VF-DE-CDS/GraphILP-API
• Documentation: https://VF-DE-CDS.github.io/GraphILP-API-docs/

Simple example

Find the smallest number of colours needed to colour the vertices of a cycle such that adjacent vertices have different colours.

import networkx as nx

from graphilp.imports import networkx as imp_nx
from graphilp.partitioning import min_vertex_coloring as vtx

G_init = nx.cycle_graph(n=5)
G = imp_nx.read(G_init)

m = vtx.create_model(G)
m.optimize()

color_to_node, node_to_color = vtx.extract_solution(G, m)

The best way to get started with GraphILP is through one of our examples.

Installation

GraphILP has two main requirements:

1. NetworkX is used internally to represent graphs. It is also the easiest way to create problem instances.
2. GraphILP creates integer linear programs in the form of Gurobi models. To create and solve these models, you need the Gurobi solver and its Python API.

Some additional libraries are required for running the examples.

You can install releases of GraphILP from PyPI via

python3 -m pip install graphilp

Alternatively, you can check out the latest development branch from the repository and add the path to your PYTHONPATH. For example:

export PYTHONPATH=$PYTHONPATH:< your path >

Licence

The GraphILP API is released under the MIT License. See LICENSE.txt for the details.

Authors

Core development team

• Rolf Bardeli [email protected]
• Richard Schmied [email protected]
• Morris Stallmann [email protected]

Contributors

• Adrian Prinz
• Thomas Sauter