6.4   Maximum Flow


This section under major construction.


Maximum flow and minimum s-t cut.

Program FordFulkerson.java computes the maximum flow and minimum s-t cut in an edge-weighted digraph in E^2 V time using the Edmonds-Karp shortest augment path heuristic (though, in practice, it usually runs substantially faster). It uses FlowNetwork.java and FlowEdge.java.

Percolation.

Max flow in 2D (always choose leftmost path) and 3D.

Applications to computer graphics.

Yuri Boykov has papers on maxflow applications to segmentation in computer vision. maxflow data.

Linear programming.

Generalization of system of linear equations to inequalities.

lecture slides

Simplex algorithm.

Invented by George Dantzig in 1948. According to Dongarra and Sullivan, the simplex algorithm is one of the top 10 algorithms with the greatest influence in science and engineering in the 20th century. Generalization of Gaussian elimination to handle inequalities. Program Simplex.java is a bare bones implementation. It solves { max cx : Ax <= b, x >= 0 } assuming that b >= 0. Hence x = 0 is a basic feasible solution (and we don't need to worry about Phase I of simplex).

Fundamental theorem of LP. Every LP of form (P) has the following three properties: (i) if it has no optimal solution, it is either infeasible or unbounded (ii) if it has a feasible solution, it has a basic feasible solution (iii) if it has an optimal solution, it has a basic optimal solution.

Strong duality theorem. Every LP of form (P) has a dual (D) { min by : y A >= c : y >= 0 }. p1 + p2 + ... + pM = 1 -> x1 + x2 + ... + xm = 1/V.

If (P) is bounded and feasible, then (D) is bounded and feasible. Moreover, they have the same optimal value. Simplex algorithm solves both problems simultaneously.

Remarkable property. In practice, simplex algorithm typically terminates in at most 2(m+n) pivots. n = total variables (original + slack), m = equations.

Pitfalls. Degeneracy, cycling.

Assignment problem.

Formulate as LP. Relies on the Birchoff-von Neumann Theorem: all extreme points of assignment problem LP are {0, 1}. AssignmentToLP.java reduces the assignment problem (max weight perfect matching) to linear programming. EasyAssignmentToLP.java puts everything in main and doesn't extract the dual solution.

Two-person zero-sum games.

Reduces to LP. Can assume payoff matrix is strictly positive (adding a constant to each entry increases the value of the game by M, but does not change the solutions). (P) min { x1 + ... + xm, : x >= 0, M^t x >= 1} and (D) max { y1 + ... + yn, : y >= 0, My <= 1}. Normalize the solution vectors x* and y* to get the row player's (minimizing) and column player's (maximizing) optimal strategies; the normalizing constant is the value of the game.

Trick. Replace variables: xi = pi / V; max V -> min 1/V; Game theory, p. 6-7

Program ZeroSumGame.java implements this approach.

Note: any LP can be put into this form by an appropriate change of variables.

The minimax theorem. (von Neumann). For every finite two-person zero-sum game, there exists a value V and a mixed strategy for each player such that (i) given the row player's strategy, the best possible payoff for the column player is V, and (ii) given the column player's strategy, the best possible payoff for the row player is -V.

OR objects.

LPDemo.java demonstrates how to solve a linear program using the OR-Objects library. It relies on or124.jar.

Exercises

  1. Cycle containing two vertices. Given an undirected graph G and two distinguished vertices s and t, find a cycle (not necessarily simple) containing s and t, or report that no such cycle exists. Your algorithm should run in linear time.

    Answer. The answer is yes if and only if the maximum flow from s to t is at least 2. So, run two iterations of Ford-Fulkerson in the digraph with each edge replace by two antiparallel edges and unit capacity.

  2. k-connected. Given an undirected graph, determine whether two vertices s and t are k-connected (or equivalently whether there are k edge-disjoint paths).
  3. Chinese postman problem. Given a strongly connected digraph G, find a directed cycle of minimum length that that traverses each edge at least once. (It turns out that the best cycle will visited each edge at most twice.) The graph is Eulerian if each vertex is balanced: its degree equals its outdegree. Divide the unbalanced vertices into two sets: L = vertices with outdegree < indegree, R = vertices with outdegree > indegree. By adding a directed path from a vertex in L to one in R, we improve the balance. Form a weighted bipartite graph on (L, R) where the weight of an edge from v to w is the length of the shortest path from v to w in G. Find a min weight matching and add these edges to G to make it Eulerian. Then, find a cycle. This is known as the Edmonds-Johnson (1973) algorithm. (Similar algorithm works for undirected graphs, but need to find a min weight perfect matching in a nonbipartite graph.)
  4. True or false. If true provide a short proof, if false give a counterexample.
    • In any max flow, there is no directed cycle on which every edge carries positive flow.
    • There exists a max flow for which there is no directed cycle on which every edge carries positive flow.
    • If all edge capacities are distinct, the max flow is unique.
    • If all edge capacities are distinct, the min cut is unique.
    • If all edge capacities are increased by an additive constant, the min cut remains unchanged.
    • If all edge capacities are multiplied by a positive integer, the min cut remains unchanged.
  5. Equality constraint. Model an equality constraint using two <= constraints.
  6. Unrestricted variables. Model an unrestricted variable x using two nonnegative variables y and z.
  7. Unbounded LP. If (P) is unbounded, then there exists a vector d >= 0 such that Ad <= 0 and cd > 0. First explain why if such a vector d exists, then the problem is unbounded. Next, modify the simplex algorithm to report such a vector when the LP is unbounded. Answer: by assumption b >= 0 and x = 0 is feasible. Thus α d is feasible for any positive constant α and has objective value α cd. The vector d can be identified by checking if the min ratio rule fails. In this case, the entries in column q are nonpositive (Ad <= 0) and the objective function coefficient is positive (cd > 0).
  8. Phase I simplex. Suppose that some coordinates of b are negative and that x = 0 is not a basic feasible solution. Describe how to find a basic feasible solution if one exists.
  9. Reduced costs. Modify the simplex algorithm to report the reduced costs (shadow prices). Give economic interpretation.
  10. Dantzig's steepest edge rule. Modify the simplex algorithm so that it always chooses the most positive objective function coefficient.
  11. Cycling. Give a pathological input that cycles.
  12. Bland's rule. Modify the simplex algorithm so that it applies Bland's rule.
  13. Bottneck assignment problem. Given N men and N women. Each person has M attributes. Each person specifies a set of desirable attributes of people of the opposite gender. Find a perfect matching in which the most unlucky person is matched with a partner with the fewest number of specified attributes. Reduce this problem to the assignment problem.

    Solution. Create an edge-weighted graph where the weight of an edge is the minimum number of desirable attributes satisfied by either person. The goal is the maximize the weight of the minimum-weigh edge in an assignment. One solution to this problem is to use binary search (eliminate all edges of weight less than a given threshold) and solve the resulting bipartite perfect matching problem.



Last modified on July 25, 2011.

Copyright © 2002–2012 Robert Sedgewick and Kevin Wayne. All rights reserved.