Multicommodity circulation formulation

Question

On the circulation problem page on wikipedia, the multicommodity circulation problem formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation problem.

I can't find any concrete description of multicommodity circulation problem to verify the correctness. There is only one paper I can find and it's behind a pay wall.

Here is a formulation I thought to make more sense:

Let $G=(V,E)$. $l_i,u,c_i:E\to \mathbb{R}$ for $1 \leq i\leq n$. We want to find a sequence of flow function $f_i$, such that:

$$ \begin{align} \text{min} & \sum_{(v,w) \in E} c_i(v,w)f_i(v,w) \\ \text{s.t.} & \sum_{(v,w) \in E} f_i(v,w) = 0 \text{ for } 1 \le i \le n, v \in V, \\ & l_i(v,w) \leq f_i(v,w) \text{ for } 1 \le i \le n, (v,w)\in E\\ & \sum_{i=1}^n f_i(v,w) \leq u(v,w) \text{ for } (v,w)\in E\\ \end{align} $$

Is this a formulation of multicommodity circulation problem?

Answer 1

I think the reference for many optimization and structural problem is Schrijver's book:

Combinatorial Optimization - Polyhedra and Efficiency

In the case, you do not have access to the book you can find his lecture notes on disjoint paths, but it's not complete, and is not comparable to the book.

Circulation is just a general definition and it's not important alone, it's important with given underling context, e.g here difference between the muticommodity circulation is just we have multiple circulation (no matter if all of them are 0), but if we want to use it for the muticommodity integer flow problem we cannot reduce it to the normal flow unless $P=NP$.

As a side note: In the Schrijver's book circulation does not include lower bound or upper bound, just flow's conservation rule holds.

This is the definition of circulation in that book:

Circulation:

Let $D = (V,A)$ be a digraph. A function $f : A \rightarrow R$ is called a circulation if

$f(\delta^{in}(v)) = f(\delta^{out}(v))$

for each vertex $v \in V$ . So now the flow conservation law holds in each vertex $v$. (in page 171)

And:

$δ^{in}(v)$ := set of arcs entering $v$,

$δ^{out}(v)$ := set of arcs leaving $v$. (in page 29)

The corresponding problem is defined as follow:

Circulation Problem:

Input: Let $D = (V,A)$ be a digraph and let $d, c : A → Q$ with $d ≤ c$.

Question: Is there a circulation $f$ satisfying $d ≤ f ≤ c$. (page 175, with a little variation).

But the minimum-cost circulation problem is as follow:

Minimum-Cost Circulation Problem:

Input: A digraph $D = (V,A)$, a demand function $d : A → Q$, a capacity function $c : A → Q$, and a cost function $k : A → Q$.

Question: Find a circulation f subject to $d ≤ f ≤ c$, minimizing $\text{cost}(f)$. (Page 177).

Finally I should mention that, I didn't see the multicommodity circulation definition (or corresponding problem) explicitly, and in my opinion, as I mentioned at start is not important alone. But I do agree with the owner of problem, that wikipedia's definition is not good, and the definition provided in this question is better and more precise than the wiki's.