[Matrix-SIG] network max-flow interesting examples?

Aaron Watters aaron@cs.rutgers.edu
Tue, 9 Jun 1998 17:10:58 -0400 (EDT)


I just posted this to sci.math.num-analysis: thought I might
as well ask the matrix-sig too: Got any good example problems
for network flow optimization? Pointers?

If anyone is interested the alpha code is at
http://athos.rutgers.edu/~aaron/MPM.py
As I say, it's not ready for prime time yet, 
and incidentally doesn't use Numeric (very set/graph
oriented ;) ).  You'd need kjbuckets or kjbuckets0 to run it.

=== post:

Hi there kind generous people!

I think I've implemented the MPM network flow maximization
algorithm described in:

V.M. Malhotra, M. Pramodh-Kumar and S.N. Maheshwari
"An O(V**3) algorithm for finding maximum flows in networks"
Information Processing Letters, 7 (1978), 277-278.

It seems to work great for the stupid tiny examples I get
out of various textbooks, but I'd really like to pound it a
bit more before releasing it.  Where can I get some good
example problems (ala the netlib LP example problems) of
interesting size and difficulty?

Please reply!  thanks.  -- Aaron Watters

"Pay no attention to the man behind the curtain!"