  


A Combinatorial Algorithm for the Multicommodity Flow Problem
Pengfei Liu (liupengfei89qq.com) Abstract: This paper researches combinatorial algorithms for the multicommodity 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 pseudoflow}, is introduced. Then we design a combinatorial algorithm to obtain equilibrium pseudoflow. If the equilibrium pseudoflow is a nonzeroequilibrium pseudoflow, there exists no feasible solution for the multicommodity flow problem; if the equilibrium pseudoflow is a zeroequilibrium pseudoflow, there exists feasible solution for the multicommodity flow problem and the zeroequilibrium pseudoflow is the feasible solution. At last, a \emph{nonlinear} description of the multicommodity flow problem is given, whose solution is equilibrium pseudoflow. Besides, the content in this paper can be easily generalized to minimum cost multicommodity flow problem. Keywords: combinatorial algorithm, multicommodity flow Category 1: Network Optimization Category 2: Combinatorial Optimization Citation: Download: Entry Submitted: 04/18/2019 Modify/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  