# Optimization Techniques for Design Problems in Selected Areas in WSNs: A Tutorial
## 4 Network Flow Programming Models
### Special Classes of NFPs
#### 4.2.5 Maximum Flow Problems  
Many situations can be modeled by a network in which the arcs may be thought of as having a capacity that limits the quantity of a product that may be shipped through the arc. In these situations, it is often desired to transport the maximum amount of flow from a starting point, which is the source node, to a terminal node which is the sink node. These problems are defined as maximum flow problems.  
The maximum flow problem again fits the NFP structure. With one exception, only the arc capacities or upper bounds are the relevant parameters. The problem is to find the maximum possible flow from a given source node \(s\) to a given sink node \(t\). An NFP model with node 1 as the source and node 8 as the sink is depicted in Figure 7. All arc costs are zero with the exception that the cost on the arc leaving the sink is set to \(-1\). Since the objective is to minimize cost, the maximum possible flow is delivered to the sink node. By convention, we assign a large number M to the upper bound on flow into the source and out of the sink node.  
The solution to the example is given in Figure 8. The maximum flow from node 1 to node 8 is 30. The individual arc flows that yield this result are shown in parentheses. The bold arcs in the figure, ((1,3), (2,6), (2,7), (5,8)), are called the _minimal cut_. In general, a cut is a set of arcs such that if they are removed from the graph, no flow can pass from the source to the sink. A cut partitions the nodes in a graph into two disjoint subsets or subgraphs. The arcs in the minimal cut 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 in this example is not a coincidence. It is always the case and is a famous primal-dual result in network theory called the max-flow min-cut theorem. The arcs comprising the minimal cut can be identified using sensitivity analysis. This problem can be solved efficiently by a classical algorithm known as the _Ford-Fulekerson Method_ which has a worst case complexity \(O\left(n.m\right)\) where \(n\) is the number of nodes and \(m\) is the number of arcs.  
**Example for a Possible Application to WSN**: An obvious possible application for this type of problems in WSNs is in routing traffic from a single source sensor node that senses a required phenomenon and transmitting the corresponding packets through the WSN where _bifurification_ of packets are allowed, down to a single sink sensor node. The maximization of the flow here, would be a maximization of the throughput received by the sink from the WSN from the original source sensor node given the constant finite link capacities that are limited by the transmission power of each sensor node in the network, the channel gain and the channel bandwidths ( obtained from Shannon-Hartley relation). There are no relevant costs for the links over here, and each link is assigned one channel to transmit on, and is not reused by any other links.  
Figure 8: Maximum flow (minimal cut) = 30.  
Figure 7: NFP model of a maximum flow problem.