A Robust Optimization Approach to Flow Decomposition

Abstract In this paper, we generalize the minimum flow decomposition problem (MFD) to incorporate uncertain edge capacities and tackle it from the perspective of robust optimization. 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. MFD problems permeate multiple important applications, including reconstructing genomic sequences to representing the flow of goods or passengers in distribution networks. Inspired by these applications, we generalize the MFD to an inexact case with bounded 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 bounds and applying different robustness concepts to handle the uncertainty. Finally, we present two different adjustably robust problem formulations and perform computational experiments illustrating the benefit of adjustability.