Minimum Parametric Flow – A Partitioning Approach

Abstract

The present paper proposes a partitioning type approach for the parametric minimum flow problem which is based on the classical decreasing directed paths method. On each of its iterations, the algorithm finds a decreasing directed path from source node to sink node in a range of parametric residual networks which are consecutively defined for subintervals of the parameter values and, by decreasing the flow along the corresponding paths in the original parametric network, splits the interval of the parameter values in subintervals generated by the breakpoints of the piecewise linear parametric residual capacity function of the decreasing directed path. Further on, the algorithm reiterates for every generated subinterval in increasing order of the parameter values.