2
$\begingroup$

The multi-commodity flow problem problem statement - wiki

According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. The linear program form of this problem as given in clrs is

CLRS Linear Program Formulation

f is flow, c is capacity, u and v are vertices, d is demand, s is source, t is target(sink). We are given k commodities. i corresponds to ith commodity.

Now How does these constraints guarantee that i commodity will end up only in target of i (ti) with its respective demand (di)

Why It works for single commodity case

In single commodity case it includes all the constraints. This is popularly known as the Maximum Flow problem. The first constraint is capacity constraint, the second one is flow conservation. The fourth implies flow is non-negative.

Why There is Problem for the multi-commodity case ?

There is no constraint on target which guarantees that flow will only go into its respective case.

For instance, this seems like a simple counter example:

counterexample

$\endgroup$
  • $\begingroup$ Perfect! That's very helpful. I added the second image into the question. Thank you! I hope you get a useful answer soon. $\endgroup$ – D.W. May 30 '16 at 19:41
1
$\begingroup$

The linear programming formulation from CLRS is fine. There is no problem with it.

Your purported counterexample isn't a valid counterexample -- it doesn't satisfy all of the inequalities. Take a closer look at the specification of the second inequality. For instance, when we are dealing with commodity $a$ ($i=a$) it says that we should have

$$\sum_{v \in V} f_{auv} - \sum_{v \in V} f_{avu} = 0$$

for all $u \in V \setminus \{s_a,t_a\}$. In particular, consider the case $u = t_b$. We have

$$\sum_{v \in V} f_{at_bv} - \sum_{v \in V} f_{avt_b} = 0 - 2 \ne 0,$$

so the inequality is violated.

To put it in English: the second inequality requires conservation of flow for each commodity, except at that commodity's source and sink. For example, for commodity $a$, we must have conservation of flow at every vertex except $s_a$ and $t_a$. In your proposed counterexample, conservation of flow for commodity $a$ is violated at vertices $s_b$ and $t_b$; that's not allowed.

$\endgroup$

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.