Network flows

From Glossary

Jump to: navigation, search

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:

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

Personal tools