Multi-commodity Flow

Question

I have just been working on chapters of questions from the DPV textbook for my exam preparation. For one of them, I'm having some trouble but I have made some progress:

---

---

My solution:

I will be using linear programming to maximize x where SUM {flow_i(s_i, v) for all i where v are nodes connecting to source s_i} >= x * d_i

subject to the constraints

• for each edge e , f1+..fk <= c_e
• for each edge e, flow_e >= 0
• and some more constraints that I'm unsure of

I think I'm on the right track but I need some help getting a bit further. Should I be considering trying to use a super-node to reduce this to a regular max flow problem?

Any help would be great! Thank you.

Answer 1

Yes, one typical approach to multi-source, multi-sink commodity flow problems is to introduce a super-source and one super-sink. Then connect all the sources s1...sk to the super-source. Connect each sink t1,...tk to the super-sink.

Important: Give a very large capacity to all the edges leaving or entering any of the super-nodes.

Objective: Maximize the total throughoput. (Sum of flows over all edges leaving the sources 1..k)

Constraints:

Edge Capacity Constraints:

You already got this right.

• for each edge e , f1+..fk <= c_e

*Flow Conservation (Flow-in == Flow_out):*

• for each vertex v, sum of flow into v = sum of flow leaving v

Demand Satisfaction:

• for each sink t_i, sum of flow into t_i (all edges ending in t_i) >= demand_i

Non-zero flows, which you already have.

Here's one accessible lecture handout that references your specific problem. Specifically, take a look at Example 2 in the handout.