# Network flows

### From Glossary

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.