4.8 Special cases¶
Part 3 · Flows · Chapter 4 · Chapter 4: Flow models · Lecture notes, volume 3 (PDF) · Exercises: Flow models
- Several classical problems are \(\mathrm{MCF}\) models with special data; all the lower bounds are zero.
| problem | the \(\mathrm{MCF}\) model |
|---|---|
| Shortest path | \(b_s=1\), \(b_t=-1\), \(b_i=0\) otherwise; \(u_{ij}=+\infty\), \(c_{ij}\) the length of the arc: the unit of flow travels from \(s\) to \(t\). |
| Maximum flow | \(b_i=0\) and \(c_{ij}=0\) for every arc, plus the arc \((t,s)\) with \(c_{ts}=-1\) and \(u_{ts}=+\infty\): the flow on \((t,s)\) is the value sent from \(s\) to \(t\). |
| Transportation | \(N=P \cup D\) with arcs from the origins \(P\) to the destinations \(D\); \(b_i\) the supply of \(i \in P\), \(-b_j\) the demand of \(j \in D\), \(u_{ij}=+\infty\). |
| Assignment | a transportation model with \(|P|=|D|\), \(b_i=1\) for \(i \in P\) and \(b_j=-1\) for \(j \in D\). |
- In the four models the balances and the bounds are integer, so the integer vertices of Theorem 4.15 are paths, integer flows and assignments.
Shortest path, maximum flow, transportation and assignment are minimum cost flow models with special balances, capacities and costs.