Max-Flow and Multicommodity-Flow problems

Links

• CS261: Optimization and Algorithmic Paradigms by Prof. Serge Plotkin
• CS363:Network Optimization -- Algorithms for network optimization problems by Prof. Serge Plotkin
• "Introduction to Algorithms" by Cormen, Leiserson and Rivest, MacGrawHill/MIT press, chapter 27, pages 579-631.

Max-Flow

If we want to find what is the maximum flow that can be flowing from a source s to a destination t in a network, where links (called edges) are directional and have a maximum transmission capacity (see figure), there is a well-known set of theorems and algorithms that apply.

In case we have several sources and several destinations we can always create two new nodes S' and T' and connect all the sources to S' and all the destinations to T'. These new edges can also have a capacity that reflects how much traffic the source can produce or the sink can absorve. Note that with the Max-Flow algorithms one calculates the global maximum, where there is no guarantee that a particular source-destination pair will have a given amount of traffic between them. Basically we are maximizing the total flow. If we want to have a traffic matrix for all source-destination pairs we have a multicommodity-flow proble. See next section for this.

Here are some definitions used in this page. Note the definitions for capacity, flow, feasible flow, residual capacity and cut.

This handout presents three basic algorithms used to find the Max-Flow/Min-Cut, with the corresponding cost and type of network when they work the best. Notes, m is the number of edges, n is the number of edges, U is the maximum capacity of any edge.

The Max-Flow and Min-Cut Theorem basically says that f is a max-flow <=> there is a cut C such that <=> there are no augmentating paths in the residual path Gf. In other words, if we find the max-flow, there is a minimum cut defined by the flow and vice-versa.

The Push-Relable algorithms solve the max-flow/min-cut problem faster. Basically one uses non feasible flows (where the flow conservation law is not observed), where we push this unrealistic flow. Then we try to realocate the flow so that we get a feasible flow (this is the relabeling). This algorithm works better when there are big differences between the capacities of the links.

Multicommodity-Flow problems

The problem that we want to solve is to minimize the cost of a flow, given a traffic matrix between sources and destinations. This flow can be decomposed along the different paths from the source to the destination, as long as they are feasible (i.e. they have to be possitive). Let's call yi the flow along the path i. Then the objective funtion is min{y`*b}, given the constraints y`*A=C and y>=0, where y`is the transpose of matrix y. b is the set of costs for each path, C is the values of the traffic matrix and A has a 1 for all paths that start and end in a particular (source, sink) pair, and a 0 elsewhere. This is a typical Linear Programming (LP) problem.

We need to know two things whether there is a feasible feasible solution first (i.e. if the intersection of the set of constraints is not empty), and then what the solution is.

There are three very well-know algorithms for solving an LP problem. These are the simplex, developed in the 40's and of NP complexity, the ellipsoid, from the 70's and P-complex, and the interior point, from the 80's and P-complete.

The LP problams they always have a dual problem that we can attempt to solve if the primal problem is too complex. Follow these links for more information on the LP Primal and Dual problems and on how the Primal and Dual solutions relate.