EURO 2025 Leeds
Abstract Submission

2816. Mixed integer linear formulation for minimum flow decomposition via column generation

Invited abstract in session MC-56: Methods & Models in Computational Biology, stream Computational Biology, Bioinformatics and Medicine.

Monday, 12:30-14:00
Room: Liberty 1.11

Authors (first author is the speaker)

1. Fernando Hugo Dias
Department of Mathematics and Systems Analysis, Aalto University
2. Tuomas Porkamaa
Aalto University
3. Philine Schiewe
Department of Mathematics and Systems Analysis, Aalto University

Abstract

Minimum flow decomposition (MFD) is a classic problem in mathematics and combinatorial optimization, which goal is to find the smallest set of paths that completely decompose a flow. Since this problem and its variants are NP-hard, exact solvers for MFD struggle to scale to large instances and cannot be efficiently generalized for practical applications.

In this work, we present an integer linear programming (ILP) formulation for MFD that tackles the challenge of encoding multiple solution paths by using column generation. With this technique, we can optimize which paths are essential towards an optimal decomposition, eliminating many hurdles that compromise the efficiency of previous models.

Our numerical results demonstrate that this approach has the potential to outperform previous state-of-the-art methods (both existing ILP formulation and algorithmic solutions) and can also be quickly and efficiently adapted to various practical variants, such as incorporating subpaths or minimizing flow errors. In comparison, while competing exact methods often struggle to optimally solve large instances, and heuristic methods may return suboptimal solutions, our findings provide a newer and more efficient tool for addressing larger instances and different variants of these problems without compromising performance and optimality.

Keywords

Status: accepted

Back to the list of papers