The Maximum Flow ProblemThe historically first and most fundamental network flow problem is theMaximum Flow Problem.ModelGiven a network with N nodes and links among them. We would like totransport some entity (for example, data) from a source node to a desti-nation node so that it flows along the links. The goal is to determine themaximum possible amount of flow that can be pushed through the network,such that link capacity contraints are obeyed and at the intermediate nodes(also called transshipment nodes) the flow is conserved, i.e., whatever flowsinto an intermediate node, the same amount must flow out.Let us review the input for the problem, the objective and constraints andthen let us formulate it as a linear programming task.Input data:• The capacity of the i → j link is Cij≥ 0 (i, j = 1, . . . , N).• There are two distinguished nodes: the source (s) and the destination(d).Remarks:• The links are directed in this model, Cijand Cjimay be different.• If the link from i to j is missing from the network, then Cij= 0 . Thus,the capacities automatically describe the network topology, too.Constraints:• Capacity constraint: The flow on each link cannot exceed the capacityof the link.• Flow conservation: The total outgoing flow of a node is equal to thetotal incoming flow of the node, except for the source and the destina-tion.Objective:Find the maximum amount of flow that can be sent through the network fromthe source to the destination, such that the link capacity is not exceeded onany link and the flow conservation constraint is satisfied at every intermediate(transshipment) node.LP FormulationLet xijdenote the flow on link (i, j). (The values of these variables are notknown in advance, we want to optimize them.)Let us express the constraints:• The flow is nonnegative (by definition):xij≥ 0 (∀i, j)• Capacity constraints:xij≤ Cij(∀i, j)• Flow conservation:NXj=1xij−NXk=1xki= 0 (∀i 6= s, d)Here the first sum is the total flow out of node i, the second sum is thetotal flow into node i.The objective function is the total net flow out of the source:F =NXj=1xsj−NXk=1xksThus, the LP formulation is:max F =NXj=1xsj−NXk=1xkssubject toNXj=1xij−NXk=1xki= 0 (∀i 6= s, d)xij≤ Cij(∀i, j)xij≥ 0 (∀i, j)SolutionSolving the Maximum Flow Problem directly as a linear program, althoughpossible, is not economical. There are several special algorithms which utilizethe special structure of the problem and, therefore, are faster and simplerthan a general LP solution.The historically first and most fundamental maximum flow algorithm is dueto Ford and Fulkerson. The key idea of the algorithm is that if we can find aso called augmenting path, then the flow can be increased without violatingany constraints.An augmenting path is any undirected path from s to d, such that on anyforward edge (an edge whose direction agrees with the path traversal) theflow is less than the capacity, while on any backward edge (an edge withopposite direction to the path traversal) the flow is positive.If such an augmenting path is found then by increasing the flow on theforward edges and decreasing with the same amount on the backward edgeswe can increase the net flow out of the source, without constraint violation.An augmenting path, if exists, can be found by a shortest path computationin an auxiliary graph, called residual graph, which is easily constructed fromthe original, using the current flow. If no augmenting path exists, then theflow is necessarily maximum.The details of the Ford-Fulkerson algorithm are presented in the next set ofslides (optional).Three important related results are summarized in the following theorems.The first is concerned with the number of iterations (augmentations) thealgorithm has to do in the worst case. Simple examples show that withunlucky choices for the augmenting paths the number of iterations can growexponentially. On the other hand, one can easily avoid this, as shown in thefollowing theorem.Theorem 1 If among the possible augmenting paths in the residual grapha shortest path is chosen in every iteration, then the algorithm reaches themaximum flow after at most nm/4 iterations, where n is the number of nodesand m is the number of edges in the graph.Note: This variant of the Ford-Fulkerson method is often called Edmonds-Karp algorithm.Another important result is the famous Max Flow Min Cut Theorem.Theorem 2 The value of the maximum flow from s to d is equal to theminimum capacity of any cut which separates d from s.Note: Since no more flow can be pushed through any cut than its capacity,therefore, the total s → d flow can never be larger than the capacity of anys → d cut (a cut that separates d from s). That is, for any feasible value Fof the s → d flow and for any s → d cut with capacity CF ≤ Calways holds. The nice thing is that if we maximize the lefthand-side andminimize the righthand-side, then we get precise equality. In other words,whatever is not obviously excluded by the capacity limitations, can actuallybe achieved. There is no gap here between the theoretically possible and thepractically achievable.Yet another important result is about the integrality of the maximum flow.Theorem 3 If all capacities are integers, then there exists a maximum flowin which the value of the flow on each edge is an integer (and, therefore, thetotal flow is also integer). Such an integer flow can also be efficiently foundby the Ford-Fulkerson or Edmonds-Karp algorithms.Note: This integrality theorem makes it possible to use maximum flow com-putations for solving graph optimization problems. Examples are the max-imum number of independent paths or the maximum matching problem inbipartite graphs. See details in the slide set entitled ”Application of Maxi-mum Flow to Other Optimization
View Full Document
Unlocking...