Search code examples
constraintslinear-programmingmax-flow

Multi-commodity Flow

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:

DPV 7.20

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.

Solution

  • 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.