- A Combinatorial Algorithm for the Multi-commodity Flow Problem Pengfei Liu (liupengfei89qq.com) Abstract: 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. Keywords: combinatorial algorithm, multi-commodity flow Category 1: Network Optimization Category 2: Combinatorial Optimization Citation: Download: Entry Submitted: 04/18/2019Entry Accepted: 05/01/2019Entry Last Modified: 05/01/2019Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.