This is an assignment of arc values, called flows, say for the k-th arc, that satisfy two types of constraints: (1) arc bounds, and (2) node balances, The flow out of node can be expressed as and the flow into node can be expressed as
If is a supply at node (called a supply node); if is a demand at node (called a demand node). If node is simply a transshipment node, and the balance equation says that the flow into node must equal the flow out of node Another way to express the node flow balance equations is with the node-arc incidence matrix:
Still another representation is to define flow variables, on which describes how much flow goes from node to node 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 but the node equations have a different form:
The (linear) min cost network flow problem is to minimize total cost, where is a unit cost of flow, subject to the flow bounds and balance equations.