  Minimum flow decomposition (MFD) -- the problem of finding a minimum set of
weighted source-to-sink paths that perfectly decomposes a flow -- is a
classical problem in Computer Science, and variants of it are powerful models
in different fields such as Bioinformatics and Transportation. Even on acyclic
graphs, the problem is NP-hard, and most practical solutions have been via
heuristics or approximations. While there is an extensive body of research on
acyclic graphs, currently, there is no \emph{exact} solution on graphs with
cycles. In this paper, we present the first ILP formulation for three natural
variants of the MFD problem in graphs with cycles, asking for a decomposition
consisting only of weighted source-to-sink paths or cycles, trails, and walks,
respectively. On three datasets of increasing levels of complexity from both
Bioinformatics and Transportation, our approaches solve any instance in under
10 minutes. Our implementations are freely available at
github.com/algbio/MFD-ILP.
