A robust optimization approach to flow decomposition

Moritz Stinzendörfer, Philine Schiewe, Fabricio Oliveira

Published 2024-10-28Version 1

In this paper, we consider a variant of the so-called minimum flow decomposition (MFD) problem in which uncertainty regarding edge capacities is taken into account from a robustness perspective. In the classical flow decomposition problem, a network flow is decomposed into a set of weighted paths from a fixed source node to a fixed sink node that precisely represents the flow distribution across all edges. While MFDs are often used in bioinformatics applications, they are also applicable in other fields, such as flows of goods or passengers in distribution networks, where the decomposition represents the vehicles and corresponding capacities needed to cover these flows. We generalize this problem to the weighted inexact case with lower and upper bounds on the flow values, provide a detailed analysis, and explore different variants that are solvable in polynomial time. Moreover, we introduce the concept of robust flow decomposition by incorporating uncertain flows and applying different robustness concepts to handle the uncertainty. Finally, we present two different adjustable problem formulations and perform computational experiments illustrating the benefit of adjustability in the uncertain case in a subsequent computational study.