Accelerating ILP Solvers for Minimum Flow Decompositions Through Search Space and Dimensionality Reductions

Andreas Grigorjew, Fernando H.C. Dias, Andrea Cracco, Romeo Rizzi, Alexandru I. Tomescu

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

17 Lataukset (Pure)

Abstrakti

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 34× on average on the hardest instances. Moreover, we show that our optimizations apply also to MFD problem variants, resulting in speedups that go up to 219× 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.

AlkuperäiskieliEnglanti
Otsikko22nd International Symposium on Experimental Algorithms, SEA 2024
ToimittajatLeo Liberti
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (elektroninen)978-3-95977-325-6
DOI - pysyväislinkit
TilaJulkaistu - heinäk. 2024
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaInternational Symposium on Experimental Algorithms - Vienna, Itävalta
Kesto: 23 heinäk. 202426 heinäk. 2024
Konferenssinumero: 22

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
Vuosikerta301
ISSN (painettu)1868-8969

Conference

ConferenceInternational Symposium on Experimental Algorithms
LyhennettäSEA
Maa/AlueItävalta
KaupunkiVienna
Ajanjakso23/07/202426/07/2024

Sormenjälki

Sukella tutkimusaiheisiin 'Accelerating ILP Solvers for Minimum Flow Decompositions Through Search Space and Dimensionality Reductions'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä