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.
Send x units of flow from s to t as cheaply as possible.
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.