[Lemon-user] optimizing maxflow/preflow speed with GLPK or MKL?

[Carlos Carroll]

For a problem in conservation planning, we are using LEMON's maximum-flow
(preflow) algorithm to derive a metric known as "flow betweenness
centrality", which involves calculating the maximum-flow flowMap between all
node pairs.
(Freeman L C, Borgatti S P and White D R (1991).  'Centrality in valued
graphs: A measure of betweenness based on network flow'.  Social Networks
13, 141-154.)
Computation time appears to scale approximately n^2.5. Therefore, as we
would like to analyze networks of ~100,000 nodes, we are looking to decrease
computational time. Our first step will be to utilize multi-threading. But I
was wondering if as a next step, we would get benefits from building the
function against either 1) the solvers discussed in the LEMON documentation
(probably limited to GLPK, as our application is open-source), or 2) other
optimization libraries, such as the Intel Math Kernel Library (MLK). Has
anyone successfully optimized maxflow in this way, or is the existing
function already as fast as feasible? Thanks in advance for information.
_____

Carlos Carroll, Ph.D.
Klamath Center for Conservation Research 
PO Box 104 
Orleans, CA 95556