An Approximate Method for Optimization of a Network Flow With Inverse Linear Constraints


Vassil Sgurev, Atanas T. Atanassov




The paper studies the opportunity for finding approximate optimum solutions in a network flow with inverse linear constraints (ILC-flow). The efficient substitution of inverse linear constraints with arc capacities of the classic network flow is the cornerstone of the proposed method. Each realization of the classic network flow is proved to be at the same time a realization of the ILC-flow. An iterative algorithm for obtaining a approximate solutions of minimum ILC-flow problems and minimum ILC- flow with minimum cost problems is considered. Exact methods and algorithms for optimization of the classic network flow are applied. Computational results are reported