# Fast Algorithms for Min-cost Multicommodity Flow Problem with Most Arcs Having 0 cost

I have a min-cost multicommodity flow problem with the following characteristics:

• Flows can be fractional (integer flows not required)
• Set of commodity types is $$K$$, set of demand nodes is $$\\{ d_k : k\in K \\}$$
• A supply node $$v$$ can supply supply up to $$b_{v, k}$$ amount of commodity $$k\in K$$
• A demand node $$d_k$$ has demand for $$\overline{d}_k$$ units of commodity $$k\in K$$, and nothing else (i.e. only commodities of type $$k\in K$$ are demanded)
• Each demand-node $$d_k$$ has exactly one outgoing arc $$(d_k, d'_k)$$, which has cost $$+\infty$$ and capacity $$+\infty$$. The node $$d'_k$$ is only incident to $$d_k$$ (it does not have any other incoming arcs, and does not have any outgoing arcs).
• Every arc $$(v, w)\in E$$ has cost 0, unless $$v$$ or $$w$$ is a demand-node, in which case there is a strictly positive cost.
• Costs are per-unit of flow on the arc, and are the same regardless of which commodity is flowing across it.
• For each arc $$(v, w)\in E\setminus \{(d_k, d'_k)) : k\in K\}$$, there is a finite capacity.

Given this structure of most of the arcs having zero (homogeneous) cost, are any algorithms or results which are particularly well-suited to my problem? Exact or approximation algorithms are both valued.

• Since you indexed the demand nodes by $K,$ should we assume that each demand node has demand for exactly one commodity and each commodity is demanded at exactly one node? What about supply nodes? Does more than one supply node handle a given commodity, and does a supply node supply more than one commodity? If the latter is true, do they have separate capacity limits for each commodity or one overall capacity limit or what?
– prubin
Commented Mar 1 at 21:28
• @prubin I edited my question to address most of your questions. Regarding your questions about supply nodes, I believe they can be addressed by simply creating a super-source node with appropriate capacities on the super-source node's edges. Commented Mar 1 at 22:41
• Since you used the word "outgoing", I assume when you say "edge" you mean "arc" (directional). Are the nonzero arc costs per unit of flow, and are they the same regardless of which commodity is flowing across the arc? Also, can we assume that there are no capacity limits on arcs?
– prubin
Commented Mar 1 at 23:34
• @prubin Thank you for pointing out the missing information. I have updated my question accordingly to address the questions you raised. Commented Mar 2 at 18:41

## 1 Answer

I'm not sure what to make of the infinite cost arcs and associated endpoints, but as the problem is stated they can be ignored. There is no reason for them to have any flow.

Given the presence of capacity limits, I do not see any way to exploit the zero cost on most arcs. The problem can be formulated as a linear program, and LPs are generally easy to solve. Were there no capacity limits on arcs, I think the zero cost aspect might be exploited to generate a smaller LP model.

• Thanks! I think indeed the infinite cost arcs could be ignored. Could you elaborate on how we could exploit the zero cost aspect to generate a smaller LP model if there were no capacity limits? Also, to provide more context, I need to repeatedly solve a multicommodity flow LP of this type within a branch-and-bound tree. As such, even though each LP might individually be quick to solve, my goal was to see if there are ways to make each LP significantly faster to solve. Commented Mar 4 at 5:07
• If there are no capacity limits, then for each pairing of a demand node and a supply node capable of making the required commodity we just need to find the cheapest route between them and then solve a transportation problem that assigns capacities to demands based on the cost of the cheapest route. Given the zero costs, finding the cheapest route from supply s to demand d can be done by sorting the inbound arcs at d according to cost and then trying to find a (zero cost) path from s to each inbound arc in succession.
– prubin
Commented Mar 4 at 16:35