Maximum flow problem

A variation on the general minimum cost network flow problem is the problem of finding the maximum flow that can be sent between a single source and a single sink (as in the diagram below) where each arc has a capacity (shown in the diagram below next to the arc) which limits the amount of flow which can be sent down it (there being no cost associated with using the arc).

An algorithm for solving this problem was developed by Ford and Fulkerson in the mid 1950's (i.e. before they developed their "out of kilter" algorithm for solving the minimum cost network flow problem). Problems of this type are called maximum flow problems and appear, for example, in communication network planning and pipeline (gas/oil/water) network planning.

The problem shown above was solved using the package, the input being shown below.

The output is shown below.

We can see from that output that the maximum flow that can be sent between the source and the sink is 7.

Note here that there is a theorem (the min-cut max-flow theorem) that says that the maximum flow possible is equal to the capacity of the minimum cut disconnecting the source and the sink. In the above problem the min-cut corresponds to the arcs (1,2), (3,2), (3,6) and (4,5) - removing these disconnects the source and the sink (see below) and their total capacity is 7.