Efficient Models for Special Types of Non-Linear Maximum Flow Problems

Abstract—In this paper, we consider the maximum flow prob-lem on networks with non-linear transfer functions. We consider special types of transfer functions, which are particularly relevant for applications. For concave transfer functions, we reduce the NL-flow problem to the generalized flow problem and solve it using a polynomial-time approximation scheme. For convex, s-shaped and monotonically growing piecewise linear (PWL) transfer functions (the latter can always be divided into s-shaped fragments), we present an equivalent network representation that allows us to build a MILP model with a better performance than if we were using standard MILP formulations of PWL functions. The latter requires additional variables and constraints to force the correct (depending on the amount of flow) linear segment of PWL functions to be taken. In our model, the correct segment in an s-shaped fragment is chosen automatically due to the network’s structure. For the case when transfer functions are non-linear, we provide an error estimation for the approximated solution. I