Maximum flows in parametric dynamic networks with lower bounds

Abstract

This paper presents and solves the problem of the maximum flow in parametric dynamic networks with nonzero lower bounds. It also provides a rigorous formulation of the problem of the maximum flow in dynamic networks and in static parametric networks, both with nonzero lower bounds. The aim of this paper is to present a novel and efficient algorithm which is developed for solving the problem of maximum flow in parametric dynamic networks with nonzero lower bounds. The proposed approach consists in applying an algorithm for finding the maximum parametric flow in a reduced expanded network, i.e. the static network obtained by expanding the original dynamic network. The article also presents a numerical example on how the algorithm works in a dynamic network having dynamic upper bounds which vary linearly with a parameter.