Integer linear programs for graph problems

GraphILP is a Python API to automatically cast graph-related optimisation problems into integer linear programming (ILP) instances. See the Introduction to get an idea of the relationship between optimisation problems on graphs and ILPs. It also lists a number of examples that are ideal for a quick start with GraphILP.

• Introduction
  • How to use
  • Examples
• Source Code

Modules

• Covering
  • Dominating set
  • Edge dominating set
  • Vertex cover
  • Knapsack
  • k-Cover
  • Set cover
  • Details
• Cuts and Flows
  • Bisection
  • Cuts
  • Flows
  • Details
• Imports
  • ILPGraph
  • NetworkX
  • Graph file formats
  • ILPSetSystem
  • Details
• Matching
  • General matching
  • Perfect matching
  • Bipartite matching
  • Details
• Networks
  • Steiner Tree Problem
  • Prize Collecting Steiner Tree (PCST)
  • Travelling Salesman Problem (TSP)
  • Details
• Packing
  • Independent set
  • Clique packing
  • Set packing
  • Details
• Partitioning
  • Vertex colouring
  • Details
• Sub- and supergraphs
  • Clique
  • Details