### Maximum Flow Problem

The maximum flow problem is again structured on a network; but here the arc capacities, or upper bounds, are the only relevant parameters. The problem is to find the maximum flow possible from some given source node to a given sink node. A network model is in Fig. 17. All arc costs are zero, but the cost on the arc leaving the sink is set to -1. Since the goal of the optimization is to minimize cost, the maximum flow possible is delivered to the sink node.

Figure 17. Network model for the maximum flow problem.

The solution to the example is in Fig. 18. The maximum flow from node 1 to node 8 is 30 and the flows that yield this flow are shown on the figure. The heavy arcs on the figure are called the minimal cut. These arcs are the bottlenecks that are restricting the maximum flow. The fact that the sum of the capacities of the arcs on the minimal cut equals the maximum flow is a famous theorem of network theory called the max flow min cut theorem. The arcs on the minimum cut can be identified using sensitivity analysis.

Figure 18. Solution. Maximum flow = 30.