flowpaths Python Package

This package implements various solvers for decomposing a weighted directed acyclic graph (DAG) into weighted paths, based on (Mixed) Integer Linear Programming ((M)ILP) formulations. It also supports the easy creation of solvers for new decomposition models.

Installation

pip install flowpaths

Basic usage example:

import flowpaths as fp
import networkx as nx

# Create a simple graph
graph = nx.DiGraph()
graph.add_edge("s", "a", flow=2)
graph.add_edge("a", "t", flow=2)
graph.add_edge("s", "b", flow=5)
graph.add_edge("b", "t", flow=5)
# ...

# Create a Minimum Flow Decomposition solver
mfd_solver = fp.MinFlowDecomp(graph, flow_attr="flow") 

mfd_solver.solve() # We solve it

if mfd_solver.is_solved(): # We get the solution
    print(mfd_solver.get_solution())
    # ([['s', 'b', 't'], ['s', 'a', 't']], [5, 2])

Design principles

1. Easy to use: You just pass a directed graph to the solvers (as a networkx DiGraph), and they return optimal weighted paths. See the examples folder for some usage examples.

2. It just works: You do not need to install an (M)ILP solver. This is possible thanks to the fast open source solver HiGHS, which gets installed once you install this package.

   • If you have a Gurobi license (free for academic users), you can install the gurobipy Python package, and then you can run the Gurobi solver instead of the default HiGHS solver by just passing the parameter external_solver="gurobi".

3. Easy to implement other decomposition models: We provide an abstract class modeling a generic path-finding MILP (AbstractPathModelDAG), which encodes a given number of arbitrary paths in the DAG. You can inherit from this class to add e.g. weights to the paths, and specify various constraints that these weighted paths must satisfy, or the objective function they need to minimize or maximize. See a basic example of a solver implemented in this manner. This abstract class interfaces with a wrapper for both MILP solvers, so you do not need to worry about MILP technicalities. The decomposition solvers already implemented in this package use this wrapper.

4. Fast: Having solvers implemented using AbstractPathModelDAG means that any optimization to the path-finding mechanisms benefits all solvers that inherit from this class. We implement some "safety optimizations" described in this paper, based on ideas first introduced in this paper, which can provide up to 1000x speedups, depending on the graph instance, while preserving global optimality (under some simple assumptions).

Models implemented:

• Minimum Flow Decomposition: Given a DAG with flow values on its edges (i.e. at every node different from source or sink the flow enetering the node is equal to the flow exiting the node), find the minimum number of weighted paths such that, for every edge, the sum of the weights of the paths going through the edge equals the flow value of the edge.
• $k$-Least Absolute Errors: Given a DAG with weights on its edges, and a number $k$, find $k$ weighted paths such that the sum of the absolute errors of each edge is minimized.
  • The error of an edge is defined as the weight of the edge minus the sum of the weights of the paths going through it.
• $k$-Minimum Path Error: Given a DAG with weights on its edges, and a number $k$, find $k$ weighted paths, with associated slack values, such that:
  • The error of each edge (defined as in $k$-Least Absolute Errors above) is at most the sum of the slacks of the paths going through the edge, and
  • The sum of path slacks is minimized.