0
votes

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.

Counter Example

Counter Example

What's stopping this to happen?

1

1 Answers

0
votes

Conservation for good a is violated at t_b, where there is a nonzero excess, because the conservation constraints are per-good and exclude only the source and sink for that good. Likewise for good b.