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

[Alpár Jüttner]

Hi Carlos,

On Tue, 2010-05-25 at 09:26 -0700, Carlos Carroll wrote:
> 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),

In fact, CLP (https://projects.coin-or.org/Clp) is also supported by
LEMON thus you can use it as well in open source projects.

Our max-flow (and min-cost flow) implementation should be much faster
then using a generic LP solver. I can't even see any possibility of
speeding up some part of the algorithm by an LP solver.


>  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.

MLK might be utilized to speed up some internal parts of the the flow
algorithm but it would require major changes in the core and I would not
expect a huge improvement. 

Instead I would suggest doing parallel execution on a higher level (i.e.
run several max flow instances in parallel).

You can also try to play with the compiler optimization flags, like
switching on loop vectorization, auto parallelization or profile based
compilation.

Of course all these trick will result in a constant factor improvement
only by utilizing the multi threading capability of the processors.

I don't know the exact way how you use the fax flow alg., but in some
cases you can use the Circulation class instead of Preflow, which can be
faster if you only want to find a feasible flow instead of a maximum
one. Or, if you only need the value of a maximum flow (plus the minimum
cut) then you can run the first phase of Preflow only.

I hope this helps.

Regards,
Alpar

p.s. Your research (and the use of LEMON for this purpose) is really
exciting. It would be great if you could keep us informed about your
progress and experience with LEMON.