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!

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:

<quote>

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

<end-quote>

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

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

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

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

Thanks!

I believe this explanatio answers my questions!

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

Great!

Thanks!