2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I would think there is still a benefit to write down the most general form for what we considers multicommodity circulation, and then we can say anything that doesn't have that form are not a multicommodity circulation problem. It is confusing when wiki reduces multicommodity flow to multicommodity circulation, there is no lower bound for each individual flow, thus demand satisfaction for the flow problem can't be resolved this way. $\endgroup$ – Chao Xu Jun 29 '13 at 20:31
  • $\begingroup$ @ChaoXu, In some sense you are right, but as I mentioned circulation is not important alone, it has meaning with transposition or flow or .... but if you want to edit wiki, I'd offer you to read the definition in the schrijver's book, or I'll write down the exact definition later in my answer. $\endgroup$ – user742 Jun 30 '13 at 14:52
  • $\begingroup$ @ChaoXu, I updated the answer, there is nothing about weights or flow in definition of circulation. Also there is no lower bound or upper bound. $\endgroup$ – user742 Jul 3 '13 at 13:02
  • 1
    $\begingroup$ Thanks for finding the reference. I think there is a misunderstanding. The circulation problem on wikipedia is stating a problem, but here the circulation is defining a function. Both have the same name, but one is a problem one is a type of function. In my question I have used the two ambiguously, I should go and make some changes. $\endgroup$ – Chao Xu Jul 5 '13 at 18:42
  • $\begingroup$ @SaeedAmiri, Chao Xu's comment is correct. You are merely defining a circulation. A circulation problem is to find this function given constraints! $\endgroup$ – Nicholas Mancuso Jul 5 '13 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.