Minimum flow decomposition in graphs with cycles using integer linear programming

Thumbnail Image

Files

Minimum_flow_decomposition_in_graphs_with_cycles_using_integer_linear_programming.pdf (1.09 MB)

Access rights

openAccess
CC BY
publishedVersion

URL

Journal Title

Journal ISSN

Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025-12

Department

Department of Mathematics and Systems Analysis

Major/Subject

Mcode

Degree programme

Language

en

Pages

32

Series

Journal of Global Optimization, Volume 93, issue 4, pp. 1145-1176

Abstract

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 a 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 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 12 minutes. Our implementations are freely available at https://github.com/algbio/MFD-ILP.

Description

Publisher Copyright: © The Author(s) 2025.

Keywords

Bioinformatics, Flow Decomposition, Integer Linear Programming, Network Flow, Transportation Science

Other note

DOI

10.1007/s10898-025-01556-8

Citation

Dias, F H C, Williams, L, Mumey, B & Tomescu, A I 2025, 'Minimum flow decomposition in graphs with cycles using integer linear programming', Journal of Global Optimization, vol. 93, no. 4, pp. 1145-1176. https://doi.org/10.1007/s10898-025-01556-8

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202601021022

Collections

[article-cris] Perustieteiden korkeakoulu / SCI