Original title: Accelerating ILP solvers for Minimum Flow Decompositions through search space and dimensionality reductions
Authors: Andreas Grigorjew, Fernando H. C. Dias, Andrea Cracco, Romeo Rizzi, Alexandru I. Tomescu
The Minimum Flow Decomposition (MFD) problem involves finding the smallest set of paths that collectively carry the flow in a network. It’s a tough problem useful in RNA transcript assembly and other fields. To tackle this, researchers enhanced an existing solver for Directed Acyclic Graphs (DAGs) using various optimizations. This upgrade notably accelerates solving speed, up to 55-90 times faster on tough instances. The optimizations also extend to related MFD problem variations, achieving speedups up to 123 times on challenging cases. Additionally, they devised a reduced-dimensionality model for a variant where path weights are limited to a specific set. This model outperforms previous methods in accuracy and is significantly faster, up to ten times faster than their optimized solver, while still finding optimal solutions for most instances. This advancement brings considerable speed and accuracy improvements to solving MFD problems in various applications.
Original article: https://arxiv.org/abs/2311.10563