Remember the lastly evaluated arcs in Circulation (and in Preflow)

[Alpar Juttner]

The attached patch​ changes the behavior of Circulation class.

For each node, we now store the lastly evaluated arc, so we can continue from this arc instead of starting from the beginning when the node is evaluated again.

A test on a network of 32768 nodes and 262892 arcs (generated by netgen) shows a running time improvement of 24%. A much more comprehensive test would of course be necessary, but this number seems quite promising.

The same idea can (should?) also be applied to the Preflow class.

[Peter Kovacs]

Great!!

I would like to perform benchmark tests of this change on all min. cost flow test instances I have.

Actually, it is strange that we haven't implemented this improvement before. Although the push-relabel min. cost flow algorithm utilizes this idea from the beginning:

• http://lemon.cs.elte.hu/hg/lemon-main/rev/9c428bb2b105
• http://lemon.cs.elte.hu/hg/lemon-main/rev/22bb98ca0101

Improving Preflow would also be great. I think, other ideas listed in ticket #191 should also be considered.

[Alpar Juttner]

Replying to kpeter:

I would like to perform benchmark tests of this change on all min. cost flow test instances I have.

Great!!

I've also uploaded a proposal for a benchmark framework, see #33. It would be even greater if those tests would find their way to this framework.

Actually, it is strange that we haven't implemented this improvement before. Although the push-relabel min. cost flow algorithm utilizes this idea from the beginning:

Maybe because Circulation is older than that implementation.

Improving Preflow would also be great. I think, other ideas listed in ticket #191 should also be considered.

Yes, they should.

[Peter Kovacs]

Replying to alpar:

I've also uploaded a proposal for a benchmark framework, see #33. It would be even greater if those tests would find their way to this framework.

Thanks. I will give it a try.

[Peter Kovacs]

I made benchmark tests to evalute this proposal on all network instances we have been using for benchmarking min cost flow algorithms. The results are surprising.

In most cases, the performance of the new version is (slightly) worse, including all NETGEN instances, but on a few particular networks, it is substantially faster:

• on hard max. flow problems arising in computer vision applications (vision_rnd)
• on a special family of grid networks (grid_wide, in which the source node has O(n) outgoing arcs): the new version runs up to 50-100x faster.

I attached all results in a .zip file.

[Alpar Juttner]

Replying to kpeter:

I made benchmark tests to evalute this proposal on all network instances we have been using for benchmarking min cost flow algorithms. The results are surprising.

I think the results are reasonable. The higher the average degree of the graph is, the bigger gain we may expect. On the other hand, this approach has some inevitable overhead. There was a chance that this overhead is always compensated by the gain. Alas, it doesn't seem to be the case.

[Peter Kovacs]

Replying to alpar:

I think the results are reasonable. The higher the average degree of the graph is, the bigger gain we may expect. On the other hand, this approach has some inevitable overhead. There was a chance that this overhead is always compensated by the gain. Alas, it doesn't seem to be the case.

Should we close this ticket as "won't fixed"?

[Alpar Juttner]

Replying to kpeter:

Should we close this ticket as "won't fixed"?

Certainly we shouldn't. In general, I'm pretty reluctant to accept any performance related changes without a reproducible extensive benchmark; and also fully against rejecting one in such situation.

And also, this situation is not very clear. In some cases it is slightly worse than the current one, but on the some (hard) examples it causes dramatic improvement. So it is something that we should certainly consider.