This paper describes a local-control method for multicommodity flow problem. Both the capacity constraints and the flow conservation constraints are relaxed. If the flow exceeds the capacity on an edge, the edge would have a congestion cost. If the flow into a vertex is not equal to that out of the vertex, the vertex would have a height. Then a new conception, stable pseudo-flow, is introduced. Potential difference reduction algorithms, which don’t rely on any shortest path or augmenting path, are designed to obtain stable pseudo-flow. If the stable pseudo-flow is a nonzero-stable pseudo-flow, there exists no feasible solution for multicommodity flow problem; if the stable pseudo-flow is a zero-stable pseudo-flow, there exists a feasible solution and the zero-stable pseudo-flow is the feasible solution. Additionally, the algorithms work in a localized manner and can be efficiently implemented in parallel, which would further improve the performance.
Article
View Water Finds its Level: A Localized Method for Multicommodity Flow Problem