0
$\begingroup$

According to this slide, the following two formulations of the mincost flow problem are equivalent:

Given directed graph G = (V, E)

  • Let u denote capacities
  • Let c denote edge costs.
  • A flow of f(v,w) units on edge (v,w) contributes cost c(v,w)f(v,w) to the objective function.

...

  1. Send x units of flow from s to t as cheaply as possible.

  2. General version with supplies and demands

    • No source or sink.
    • Each node has a value b(v).
    • positive b(v) is a supply
    • negative b(v) is a demand.
    • Find flow which satisfies supplies and demands and has minimum total cost.

I can see that 2. is a special case of 3. in which only two nodes (s and t) and have non-zero demand. But I cannot figure out how to transform the more general problem 3. into problem 2.

Can anyone help explain how to transform 3. to 2. ?

That is, how to e.g. add edges and/or change capacity/cost, to solve problem 3. with a solver of problem 2.

$\endgroup$
1
$\begingroup$

I would say that 3. is a special case of 2. instead but it is a point of view.

On 3., you can create a new node "source" which has edges to every supply nodes (b(v) > 0). These edges have cost 0 and capacity b(v).

Then you create a new node "sink" which has edges from every demand node. These edges have cost 0 and capacity -b(v).

All this replaces the b(v) values which are not needed anymore.

$\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.