A Minimum Cost Relaxation Model for Infeasible Flow Networks

In many real systems, it happens that the existing flow network become inconsistent with the new applications or inputs. This means that some of the applicable structural characteristics have been changed so that the flow network has become infeasible or, in other words, obsolete. Therefore, it has to be adjusted to new applications. It is well known how to use a maximum flow algorithm to determine when a flow network is infeasible, but less known is how to adjust the structural data such that the network becomes feasible while the incurred adjustment cost is minimal. This paper considers an infeasible flow network G= (V, A) in which supplies/demands, arc capacities and flow lower bounds are liable to relax. A minimum cost relaxation model for canceling most positive cuts is constructed. Analyzing the model shows that, in order to make the network feasible, it is sufficient to adjust only one component of the structural data. According to this result, a polynomial time algorithm is developed to cancel all positive cuts and convert the infeasible flow network to a feasible one.