Parametric flows in static networks

Abstract

Parametric flow problems may be regarded as some extensions of the classical maximum/minimum flow problems in which the capacities of certain arcs are fixed but are functions of a parameter. Consequently, these problems consist of solving several nonparametric, ordinary maximum/minimum flow problems for all the parameter values within certain subintervals of the parameter values. During the last few decades, research that has been conducted resulted in new solution methods and in improvements of the algorithms for known methods. This paper presents the continuous improvements that have been made during the last years as well as recent techniques and algorithms related to parametric maximum and minimum flow problems. The paper also constitutes a synthesis of the different approaches that have been proposed by us for solving the parametric flow problem in static networks.