Network flows

This is an assignment of arc values, called flows, say $LaTeX: f(k)$ for the k-th arc, that satisfy two types of constraints: (1) arc bounds, $LaTeX: \textstyle L \le f \le U,$ and (2) node balances, $LaTeX: \textstyle \mbox{Flow out of node } i - \mbox{ Flow into node } i = b(i).$ The flow out of node $LaTeX: i$ can be expressed as $LaTeX: \textstyle \sum_k \left \{f(k): T(k)=i \right \},$ and the flow into node $LaTeX: i$ can be expressed as $LaTeX: \textstyle \sum_k \left \{f(k): H(k)=i \right \}.$

If $LaTeX: b(i) < 0, -b(i)$ is a supply at node $LaTeX: i$ (called a supply node); if $LaTeX: b(i) > 0, b(i)$ is a demand at node $LaTeX: i$ (called a demand node). If $LaTeX: b(i)=0,$ node $LaTeX: i$ is simply a transshipment node, and the balance equation says that the flow into node $LaTeX: i$ must equal the flow out of node $LaTeX: i.$ Another way to express the node flow balance equations is with the node-arc incidence matrix: $LaTeX: Mf=b.$

Still another representation is to define flow variables, $LaTeX: x(i, j)$ on $LaTeX: \textstyle V \times V,$ which describes how much flow goes from node $LaTeX: i$ to node $LaTeX: j.$ This can be used as long as there are no parallel arcs - i.e., no two arcs have both the same tail and the same head. (In some applications, parallel arcs are needed, such as to increase capacity across a pair of arcs with an increased cost.) In this form, the capacity constraints are still of the form $LaTeX: \textstyle L \le x \le U,$ but the node equations have a different form:

$LaTeX: \sum_j \left \{x(i, j): (i, j) \in A \right \} - \sum_j \left \{x(j, i): (j, i) \in A \right \} = b(i) \mbox{ for all } i \in V.$

The (linear) min cost network flow problem is to minimize total cost, $LaTeX: \textstyle \sum_{ij} \left \{c(i,j)x(i,j): (i,j) \in A \right \},$ where $LaTeX: c$ is a unit cost of flow, subject to the flow bounds and balance equations.