Learning-Augmented Robust Dynamic Network Flow With Theoretical Guarantees

Authors: G.Yuvaroopa Lakshmi, K.Saraswati, D.Sattemma

Abstract: Dynamic network flow problems are central to applications such as transportation systems, communication networks, and real-time logistics, where edge capacities and demands evolve over time under uncertainty. Traditional approaches either adopt worst-case assumptions, leading to overly conservative solutions, or rely on stochastic models that may lack strong robustness guarantees. This gap motivates the integration of predictive, data-driven insights into algorithmic frameworks while preserving rigorous performance assurances. In this paper, we present a learning-augmented robust framework for dynamic minimum cost flow problems. We consider a time-indexed networkG_t = (V,E,c_t,w_t), where capacities and costs vary dynamically, and incorporate partial forecasts provided by a machine-learned oracle. Our approach combines online primal-dual optimization techniques with robust correction mechanisms to effectively handle inaccuracies in predictions. The proposed framework treats predictions as advisory inputs while ensuring feasibility under adversarial deviations. A tuneable robustness parameter is introduced to balance efficiency and resilience, enabling improved performance when predictions are accurate and controlled degradation when they are not. We establish strong theoretical guarantees, including consistency, robustness bounds, regret analysis, and competitive ratios. These results demonstrate that the algorithm achieves near-optimal performance under accurate predictions while maintaining bounded worst-case losses under prediction errors. Experimental evaluations on dynamic transportation and communication network scenarios show that our method significantly outperforms classical robust and stochastic approaches. The results indicate improved efficiency, reduced congestion, and enhanced adaptability to real-time changes. Overall, this work highlights the effectiveness of integrating machine learning with robust optimization to address complex, time-evolving network flow challenges with both practical and theoretical reliability.

DOI: https://doi.org/10.5281/zenodo.19468932