This paper researches combinatorial algorithms for the multi-commodity flow problem. We relax the capacity constraints and introduce a \emph{penalty function} \(h\) for each arc. If the flow exceeds the capacity on arc \(a\), arc \(a\) would have a penalty cost. Based on the \emph{penalty function} \(h\), a new conception , \emph{equilibrium pseudo-flow}, is introduced. Then we design a combinatorial algorithm to obtain equilibrium pseudo-flow. If the equilibrium pseudo-flow is a nonzero-equilibrium pseudo-flow, there exists no feasible solution for the multi-commodity flow problem; if the equilibrium pseudo-flow is a zero-equilibrium pseudo-flow, there exists feasible solution for the multi-commodity flow problem and the zero-equilibrium pseudo-flow is the feasible solution. At last, a \emph{non-linear} description of the multi-commodity flow problem is given, whose solution is equilibrium pseudo-flow. Besides, the content in this paper can be easily generalized to minimum cost multi-commodity flow problem.
Article
View A Combinatorial Algorithm for the Multi-commodity Flow Problem