Accelerating ILP solvers for Minimum Flow Decompositions through search space and dimensionality reductions
Given a flow network, the Minimum Flow Decomposition (MFD) problem is finding the smallest possible set of weighted paths whose superposition equals the flow. It is a classical, strongly NP-hard problem that is proven to be useful in RNA transcript assembly and applications outside of Bioinformatics. We improve an existing ILP (Integer Linear Programming) model by Dias et al. [RECOMB 2022] for DAGs by decreasing the solver's search space using solution safety and several other optimizations. This results in a significant speedup compared to the original ILP, of up to 55-90x on average on the hardest instances. Moreover, we show that our optimizations apply also to MFD problem variants, resulting in similar speedups, going up to 123x on the hardest instances. We also developed an ILP model of reduced dimensionality for an MFD variant in which the solution path weights are restricted to a given set. This model can find an optimal MFD solution for most instances, and overall, its accuracy significantly outperforms that of previous greedy algorithms while being up to an order of magnitude faster than our optimized ILP.
Code (1)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Power Flow Feasibility Assessment Using Variational Graph Autoencoders
Data-driven methods, including graph neural networks, have been studied for accelerating power flow calculations in recent years, but very little attention has been paid to the solution feasibility, which can be obtained…
Analysis and Optimization of Graph Decompositions by Lifted Multicuts
We study the set of all decompositions (clusterings) of a graph through its characterization as a set of lifted multicuts. This leads us to practically relevant insights related to the definition of classes of decom…
Breaking Boundaries: Distributed Domain Decomposition with Scalable Physics-Informed Neural PDE Solvers
Mosaic Flow is a novel domain decomposition method designed to scale physics-informed neural PDE solvers to large domains. Its unique approach leverages pre-trained networks on small domains to solve partial differential…
scientific discoveryAccelerating Quasi-Static Time Series Simulations with Foundation Models
Quasi-static time series (QSTS) simulations have great potential for evaluating the grid's ability to accommodate the large-scale integration of distributed energy resources. However, as grids expand and operate closer t…
Time SeriesA machine learning based algorithm selection method to solve the minimum cost flow problem
The minimum cost flow problem is one of the most studied network optimization problems and appears in numerous applications. Some efficient algorithms exist for this problem, which are freely available in the form of lib…