 View Question
Q: Min-Cost Fixed Flow in Undirected graph ( Answered ,   6 Comments ) Question
 Subject: Min-Cost Fixed Flow in Undirected graph Category: Computers > Algorithms Asked by: kalitar-ga List Price: \$30.00 Posted: 17 Mar 2005 14:11 PST Expires: 16 Apr 2005 15:11 PDT Question ID: 496389
 ```I need to solve following problem. I have undirected graph, source node S, sink node T, flow X to send from S to T, capacity C(i,j) of each vertex in undirected graph and price P(i,j) for single unit of flow for each vertex. Task is to find Min-Cost flow from S to T. Flow should be of X units. There are many algorithms found by Google for Directed graph. And not much for Undirected. We can apply Directed graph algorithms for Undirected case. However I believe that Undirected graph problem is easier one and can be solved in better O(). I need online materials and algorithms for the solution of the problem. There is one algorithm that I know, but I need better one. The algorithm is as follow: 1) Find shortest path (in respect of P(i,j)) from S to T. 2) Send K unit of flow through shortest path found in 1). K is smallest C(i,j) along the path. 3) X =- K 4) If X == 0 then solution is found else goto 1) I'll appreciate your answers. Thanks!``` Subject: Re: Min-Cost Fixed Flow in Undirected graph Answered By: mathtalk-ga on 16 Apr 2005 11:17 PDT Rated: ```Hi, kalitar-ga: A nice summary of the relationship between linear programming problems generally and those which correspond to (directed) network flow problems is provided here: [Network Flow] http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE167.HTM It also provides links to some top-end implementations: The highest-performance code available for solving maximum-flow in graphs is PRF [CG94], developed in the C language by Cherkassky and Goldberg. They report solving instances with over 250,000 vertices in under two minutes on a Sun Sparc-10 workstation. For minimum-cost max-flow, the highest-performance code available is CS [Gol92], capable of solving instances of over 30,000 vertices in a few minutes on Sun Sparc-2 workstations. Both of their codes are available by ftp for noncommercial use from: http://www.neci.nj.nec.com/homepages/avg.html See the page for further links, and for descriptions of various algorithmic approaches. Let's down into the issue you specifically raise of directed versus undirected graphs, and the impact of this distinction on algorithmic complexity. It is helpful to use the framework of general linear programming problems, qv. this page from the same site as above: [Linear Programming] http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK3/NODE141.HTM The simplex algorithm to solve general linear programming problems was proposed by George Danzig in 1947: [Simplex algorithm -- Wikipedia] http://en.wikipedia.org/wiki/Simplex_algorithm [simplex algorithm -- PlanetMath] http://planetmath.org/encyclopedia/SimplexAlgorithm.html [An Introduction to Linear Programming and the Simplex Algorithm] http://www.isye.gatech.edu/~spyros/LP/LP.html While Klee and Minty, and independently Zadeh, in 1972 gave examples to show that with a simple pivot rule, the simplex algorithm is in the worst case exponential in the number of unknowns, it is suprisingly efficient in practice. More sophisticated algorithms, based in particular on the ellipsoid algorithm, have been shown to have worst case polynomial times, but in practice their performance is not generally competitive. Dantzig, G. B. (1949). Programming of interdependent activities: II mathematical model. Econometrica. 17. 200-211. Karmarkar, N. (1984). A new polynomial algorithm for linear programming. Combinatorica. 4. 373-395. Khachiyan [Hajican], L. G. (1979). A polynomial algorithm for linear programming. Soviet Mathematics Doklady. 20. 191-194. Klee, V. and G. Minty. How good is the simplex algorithm. In Inequalities III, pages 159-172, New York, 1972. Academic Press. Zadeh, N. (1972). A bad network problem for the Simplex method and other minimum cost flow algorithms. Mathematical Programming. 5. 255-266 * * * * * * * * * * * * * * * * * * * * * * In an earlier comment we reduced a min-cost capacitated problem involving an undirected graph to terms comparable to one involving a directed graph using linear programming as the framework. It is probably worth noting that the reduction can already be made at the "outer" level of the graph formulation itself at a cost of introducing one additional node per edge. That is, for each undirected edge E of the original graph, we create a synthetic node C(E) through with all flow in one direction ("backflow") is redirected: edge E A------>>-------B \ / < < < < \ / C(E) To make this work the original "backflow" capacity of is assigned to both new edges, and the per unit cost for this can be split arbitrarily between the two edges. This enlarges the problem statement, adding as it does not only a node but three directed edges where previously there was one undirected edge, but it makes clear that at most a constant multiple is involved in the size of restated problem and thus (given a polynomial complexity algorithm is available) a constant multiple in time. The insight that one gains from the linear programming restatement is that no extra nodes are really needed, only twice as many unknowns (representing the unknown flow for an edge in either direction). [A clue to this fact is given by the arbitrariness of cost-splitting between a pair of new edges.] regards, mathtalk-ga```
 kalitar-ga rated this answer:  Subject: Re: Min-Cost Fixed Flow in Undirected graph From: mathtalk-ga on 18 Mar 2005 05:39 PST
 ```Hi, kalitar-ga: You are correct to see a close connection between solving shortest path problems and the solution to the capacitated minimum cost flow problem. Perhaps the following link (to a download a PDF paper) will be helpful to you in clarifying this aspect: [A faster strongly polynomial minimum cost flow algorithm] (James B. Orlin; 1988) http://ideas.repec.org/p/mit/sloanp/2206.html The importance of shortest path algorithms is also highlighted in this more recent paper on minimum cost for submodular flows, a generalization of the minimum cost flow problem: [A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow] (Lisa Fleischer, Satoru Iwata, and S. Thomas McCormick; 1999,2001) http://www.andrew.cmu.edu/user/lkf/papers/subflow.pdf You seem to be quite familiar with the treatment of an undirected graph in terms of directed graphs (by "duplicating" edges), so please forgive me if I seem to belabor the point. I would not expect an undirected graph to be more easily solved than the equivalent (directed) network flow. While you might conceive of the problem intuitively as having fewer constraints, it has at the same time more unknowns to determine, ie. to find the direction as well as magnitude of flow along each edge. The minimum cost network flow problem has many typical features of a linear programming problem. Here feasibility corresponds to determining whether the capacities of the edges allow X units to be transported from S to T at any cost; only if the problem is feasible can we define a minimum cost solution. It is a usual tactic in linear programming problems which deal with unknowns that may not necessarily be >= 0 to impose a "standard" formulation (eg. nonnegativity constraints) by expressing each such unknown as the difference of two variables which are nonnegative. Such a reduction to standard form is necessary, for example, in order to apply primal/dual methods. regards, mathtalk-ga```
 Subject: Re: Min-Cost Fixed Flow in Undirected graph From: kalitar-ga on 18 Mar 2005 09:50 PST
 ```Orlin algorithm works only in either (i,j) or (j,i) arc is in graph, but not both. So I believe it will be hard to convert Undirected graph to directed one and use this algorith. In general if for each undirected vertex (i,j) with C(i,j) and P(i,j) and 2 directed arcs (i,j) with C'(i,j) = C(i,j) and P'(i,j) = P(i,j) and (j,i) with C'(j,i) = C(i,j) and P'(j,i) = P(i,j) will this be sufficient to solve the undirected case of the problem? Also how can express undirected case of the problem as Linear program. Thanks, Vassil```
 Subject: Re: Min-Cost Fixed Flow in Undirected graph From: mathtalk-ga on 19 Mar 2005 13:20 PST
 ```Hi, Vassil: Let's use lower case letters u,v to refer to nodes of your (undirected) graph, with special reference to the single source s (start) and single sink t (terminal). Now a "directed" edge is an ordered pair (u,v). To formulate the minimum cost fixed-flow problem as a linear program, it is not so much necessary to think of the graph as "directed" as it is to define quantities both known and unknown in terms of these ordered pairs. So consider from a mathematical point of view f(u,v) and f(v,u) (the flow from u to v and the flow from v to u) simply as distinct values. Correspondingly the capacities C(u,v) and C(v,u) may or may not be the same, and the (positive) prices per unit flow P(u,v) and P(v,u) may or may not be equal. If it suits your application to define them as equals, then let it be so. The minimum cost for a total flow of X from s to t can then be stated as this (nonstandard) linear program: Minimize SUM P(u,v)*f(u,v) (u,v) such that: SUM (f(u,v) - f(v,u)) = 0 for all u not in {s,t} v SUM (f(s,v) - f(v,s)) = X v SUM (f(t,v) - f(v,t)) = -X v 0 <= f(u,v) <= C(u,v) for all (u,v) Note that for "edges" (u,v) that are not present in the network or graph, one can simply treat these flow values f(u,v) as zero by omitting them from the equations, which would be the equivalent of setting a capacity C(u,v) = 0 for these. Note further that because prices P > 0 and we are minimizing the sum of P*f, wherever there are two unknowns f(u,v) and f(v,u), we are guaranteed that any optimum occurs with at least one of them equal to zero (as otherwise we could simply improve the objective function by subtracting the minimum of f(u,v) and f(v,u) from both of them). There is no guarantee from the mere formulation of the problem as a linear program that it has a feasible solution. After all X may exceed the maximum flow of the network. Furthermore the literature of minimum cost fixed-flow algorithms can perhaps be understood as specialized methods for solving these linear programs by exploiting shortest-path or other efficient building blocks to "drive" the linear program to an optimum. It is certainly tempting to think that when X is a low value in relationship to the network's maximum flow capacity, that one can expeditiously build a minimum cost flow up to that level through "augmenting paths" discovered by the shortest-path heuristic. On the other hand when X is very close to the maximum feasible flow, it might be more attractive to start from the max-flow/min-cut operating point and incrementally reduce costs from there by discovering the highest cost contributions to that flow. regards, mathtalk-ga```
 Subject: Re: Min-Cost Fixed Flow in Undirected graph From: kalitar-ga on 19 Mar 2005 15:18 PST
 ```Thanks! I believe this explanatio answers my questions!```
 Subject: Re: Min-Cost Fixed Flow in Undirected graph From: mathtalk-ga on 19 Mar 2005 21:45 PST
 ```Hi, Vassil: Great! Let me try to dress it up a bit with some links to downloadable code for these kinds of problems & a sketch of what's known about time complexity, and I'll post it as an Answer for you. regards, mathtalk-ga```
 Subject: Re: Min-Cost Fixed Flow in Undirected graph From: kalitar-ga on 22 Mar 2005 06:56 PST
 ```Great! Thanks!``` 