Optimization Online


A Combinatorial Algorithm for the Multi-commodity Flow Problem

Pengfei Liu (liupengfei89***at***qq.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



Entry Submitted: 04/18/2019
Entry Accepted: 05/01/2019
Entry Last Modified: 05/01/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society