COIN-OR::LEMON - Graph Library

Opened 6 years ago

Last modified 5 years ago

#431 new enhancement

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

Reported by: alpar Owned by: alpar
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

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.

Attachments (2)

23a4fa3a7e62.patch (3.9 KB) - added by alpar 6 years ago.
circulation_benchmark_201303.zip (4.0 KB) - added by kpeter 5 years ago.

Download all attachments as: .zip

Change History (11)

Changed 6 years ago by alpar

comment:1 follow-up: Changed 6 years ago by kpeter

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:

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

comment:2 Changed 6 years ago by alpar

  • Type changed from defect to enhancement

comment:3 in reply to: ↑ 1 ; follow-up: Changed 6 years ago by alpar

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.

comment:4 in reply to: ↑ 3 Changed 6 years ago by kpeter

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.

comment:5 Changed 5 years ago by alpar

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release

comment:6 follow-up: Changed 5 years ago by 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.

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.

Changed 5 years ago by kpeter

comment:7 in reply to: ↑ 6 ; follow-up: Changed 5 years ago by alpar

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.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 5 years ago by kpeter

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"?

comment:9 in reply to: ↑ 8 Changed 5 years ago by alpar

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.

Note: See TracTickets for help on using tickets.