Port the remaining min. cost flow algorithms

[Alpar Juttner]

This ticket is a follow-up of #47.

The affected files are

• lemon/cancel_and_tighten.h
• lemon/capacity_scaling.h
• lemon/cost_scaling.h
• lemon/cycle_canceling.h
• lemon/min_cost_flow.h
• lemon/min_cost_max_flow.h

[Peter Kovacs]

This task depends on #51 and #179. Maybe it would be better in 1.2.

[Peter Kovacs]

The porting of Network Simplex is separated from the other MCF algorithms, since it is the most important, and it is easier to revise the interface of a single file. See #234 for details. For now on this ticket is only about the remaining MCF algorithms.

[Peter Kovacs]

Replying to kpeter:

This task depends on #51 and #179. Maybe it would be better in 1.2.

Only BellmanFord class is needed from #51.

Apart from that StaticDigraph (#68) would be good to have for these files, too. In fact, it is not used in the current SVN versions (-r3520), but it would be much more efficient in some cases to copy the used ResidualDigraph adaptor to a StaticDigraph structure before running an algorithm (e.g. BellmanFord or MinMeanCycle) on it.

[Peter Kovacs]

To sum it up, this task depends on the following tickets:

• #51 Port BellmanFord
• #179 Port the min mean cycle algorithms
• #68 Port StaticDigraph

and finally

• #146 Cheap copy of maps (reference counting)
  Maps are usually copied using copy constructor or operator= in the current implementations in SVN, but these methods can be avoided, if it is really necessary.

#51, #68 and #179 already contain the necessary patches, they only have to be revised.

[Peter Kovacs]

I attached four patches that port, highly improve and test CapacityScaling.

Its interface became the same as NetworkSimplex's except for the support for LEQ supply type. The implementation is improved in three aspects:

1. A simple and efficient internal graph representation is used for storing the residual graph. It makes the code about 1.5-5 times faster on average.
2. The GEQ supply type is also supported, not only the EQ case. Note that it increases the running time for the EQ case about 5-8 percent (contrary to NS), since additional arcs have to be added to the digraph before the supply values are known, thus they cannot be left out for the EQ case. However this additional time could be accepted in favor of the generality, I think. Together with the above improvement, the implementation is still much faster for the EQ case, as well.
3. Negative costs are supported, but due to the characteristic of the algorithm, arcs of negative cost and infinite upper bound are not supported. The algorithm returns UNBOUNDED if such an arc exists despite the objective function could be bounded over the feasible flows in these cases, too.

[Peter Kovacs]

For the sake of convenience, I collect all my candidate pathces to this repository:
​http://lime.cs.elte.hu/~kpeter/hgwebdir.cgi/lemon-candidate/

[Peter Kovacs]

Two more changesets for CapacityScaling:

• [50d28aa826bb] It actually contains fixes for the Heap concept. Without these changes the next changeset would produce a lot of warnings, when Heap is used in the test file.
• [2ee24622f87b] Add a traits class and a named parameter to support heap changing for CapacityScaling.

[Peter Kovacs]

The attached bundle file​ contains 23 changesets, all of which is needed for porting and reworking CapacityScaling and CostScaling, but some of them are already proposed in the corresponding tickets.

The contained changesets are the followings:

• The six patches about CapacityScaling (see above).
• Six changesets about StaticDigraph (see #68), namely:
  • [cf360f758f25] Port StaticDigraphfrom SVN -r3524 (#68)
  • [f4b5c2d5449d] Small improvements + add tests for StaticDigraph (#68)
  • [6cab2ab9d8e7] Add documentation for StaticDigraph (#68)
  • [eff1caf6d32e] Extend the interface of StaticDigraph (#68)
  • [5764dd9b6e18] Add a new build() function to StaticDigraph (#68)
  • [a143f19f465b] Make some graph member functions static (#311, #68)
• [6f10c6ec5a21] Small fixes related to BellmanFord (#51)
• Six new changesets for MCF algorithms:
  • [f7ba42e51c2e] Port CostScaling from SVN -r3524 (#180)
  • [5fa1a469dc0f] Fully rework CostScaling (#180)
  • [78aed31cd30b] Add tests for CostScaling (#180)
  • [d29a1bf75606] Small implementation improvements in MCF algorithms (#180)
  • [087eb00f578c] More options for run() in scaling MCF algorithms (#180)
  • [e7878cf97a92] Small doc improvements in MCF classes (#180)
• Finally, four new 'Merge' changesets, namely: [fd26dde1739f], [e0267cc7b097], [627718e07959], [ac5e336ad116].

[Peter Kovacs]

The next bundle file​ contains two changesets: a Merge and '[bf559aafdf49] Add citations to the scaling MCF algorithms (#180, #184)'.

Note that the Merge is on the top of [ac5e336ad116] from this ticket and [134852d7fb0a] from #184.

[Peter Kovacs]

There was a small mistake in [bf559aafdf49], consider to use the new bundle file with [cded687f534a] instead.

[Peter Kovacs]

I'm currently working on the cycle canceling algorithms, so I will finish this whole task soon.

Here are the conclusions I could make:

1. Storing the residual network in an efficient internal structure results in much faster codes (even if the original graph type is SmartDigraph or StaticDigraph). For all algorithms except for NS, I used the same basic structure:
   • The nodes and arcs are represented by continuous ranges of integers.
   • Each arc is stored twice (foward and backward residual arc).
   • All related data are stored in vectors.
   • The residual arcs are stored in a specific order so that the outgoing list of each node is a continuous range, thus it can be traversed like this:

        int end = first_out[u+1];
        for (int e = first_out[u]; e != end; ++e) {
          if (res_cap[e] > 0) {
            // e is an outgoing residual arc of node u
          }
        }
     

     This results in two major advantages: 1. the iteration is much faster; 2. the related data vectors are typically used with consecutive indices. In fact, this storage is almost the same as if undirector(digraph) would be copied to a StaticDigraph structure (but the in-arc lists are omitted).

2. If I would like to perform a separate non-linear algorithm on the residual graph (e.g. BellmanFord, min. mean cycle etc.), then it is typically faster to build a StaticDigraph containing exactly the required graph than:
   • either using ResidualDigraph adaptor or
   • copying undirector(digraph) to a StaticDigraph structure only once and using it with FilterArcs adaptor each time.

3. Considering the above experiments, it would be worth to test such ideas for the maximum flow algorithms, as well. E.g., could Preflow be made faster with such ideas? I guess that it is possible for large and difficult instances. Actually, I don't think that Preflow or Circulation should copy the digraph (and its maps), but could we draft a good guideline for this question? Which algorithms are allowed/welcomed to copy the graph (and some maps on it)?

4. The GEQ supply type (see #219) will be supported by all algorithms. All of them extend the graph to compute the node potentials correctly. (It could be avoided with some work-around, but it isn't important, since the graph is copied anyway.) Therefore all algorithms are capable for supporting the LEQ supply type, as well. It would only require a careful extension of the current (non-trivial) initialization processes. Maybe, we could make a ticket about this improvement.

5. The algorithms also support negative costs and infinite upper bounds. However, note that the latter one could cause many problems even is simpler algorithms (see #319), thus the infinite upper bounds should be removed in all methods except for NetworkSimplex. That's why they don't support arcs having negative cost and infinite upper bound at once. In such cases, they return UNBOUNDED, but the objective function could actually be bounded over the feasible solutions (if there is no directed cycle of negative total cost and infinite upper bound), i.e. NS could return OPTIMAL.

[Peter Kovacs]

The attached bundle file​ contains the following eight changesets related to the cycle canceling algorithms:

• [0dcf8d92aba8] Merge
  It is on the top of [627718e07959] (see above) and [8642452f583c] from #179.
• [7e3516d503c2] Port cycle canceling algorithms from SVN -r3524 (#180)
• [dada1f331b3f] Entirely rework cycle canceling algorithms (#180)
  
  • Move the cycle canceling algorithms (CycleCanceling, CancelAndTighten) into one class (CycleCanceling).
  • Add a Method parameter to the run() function to be able to select the used cycle canceling method.
  • Use the new interface similarly to NetworkSimplex.
  • Rework the implementations using an efficient internal structure for handling the residual network. This improvement made the codes much faster.
  • Handle GEQ supply type (LEQ is not supported).
  • Handle infinite upper bounds.
  • Handle negative costs (for arcs of finite upper bound).
  • Extend the documentation.
• [2c3d5938c03c] Add tests for CycleCanceling (#180)
• [aa1f4ce75b4f] Merge
  It is on the top of the previous patch and [087eb00f578c] (see above).
• [445a1e99d3db] Rework the min cost flow test file (#180)
• [ed61814962cc] Merge
  It is on the top of the previous patch and [cded687f534a] (see above).
• [71cf7a7747bb] Add citations to CycleCanceling (#180, #184)

[Peter Kovacs]

For simpler overview, you may also find all the proposed changesets in this repository:
​http://lime.cs.elte.hu/~kpeter/hgwebdir.cgi/lemon-candidate/

[Alpar Juttner]

I'm reviewing the changesets. Some questions:

1. Are the changesets here complete in the sense that it ports all the MCF tools available in the SVN repo?
2. Some of the changesets depend on other chgsets under review in ticket #68, #311 and #51. Is there any particular reason for these dependencies?

[Peter Kovacs]

Replying to alpar:

1. Are the changesets here complete in the sense that it ports all the MCF tools available in the SVN repo?

All tools are ported, except for the two wrapper classes MinCostFlow and MinCostMaxFlow. In fact, it is a question if would like to have such tools or not. If yes, then I would like to make them heuristic to try to select the best algorithm according to the actual parameters of the problem.

I'm going to perform more comprehensive tests for MCF algorithms (using more genertors and maybe real-world instances). Based on these results, I would like to fine-tune the heuristics of all algorithms and make these wrapper classes.

2. Some of the changesets depend on other chgsets under review in ticket #68, #311 and #51. Is there any particular reason for these dependencies?

Yes, definitely. I tried to use only those patches that are really needed.

• #311: It is closed, there is no changesets under review here, except for one somewhat related changeset [a143f19f465b], that is actually attached to #68. This improvement is exploited in the MCF implementations (namely in the nested class VectorMap), but it could be avoided, if it is really needed.
• #68: The StaticDigraph structure is heavily used along with the new build() function and the interface extensions. Actually, that's the reason why I ported the structure and proposed that build() function.
• #51: Only one changeset is needed that is not merged into the main branch yet. It is [6f10c6ec5a21], from which fixing the missing include is necessary for these pathces.
• #179: The min. mean cycle classes are needed for the cycle canceling algorithms.

[Alpar Juttner]

As far as I see, all the necessary changesets are in the main branch now. Could you rework the merges?

[Peter Kovacs]

Fortunately, only the cycle canceling changesets had to be reworked. The new pathces can be found in the attached bundle file. [8563e7174b43], [88580a216e47], [ad783a4ae986], [904a1ba062b5] are the rebased versions of [7e3516d503c2], [dada1f331b3f], [2c3d5938c03c], [71cf7a7747bb]. [1d5af6bc963b] is the rebased version of [445a1e99d3db] on the top of [3f0156fe4662], which is a new merge changeset.

If the latest patch, namely [1d5af6bc963b] is merged, then all changesets will merged from this ticket as dependencies.

[Peter Kovacs]

Replying to alpar:

milestone changed from LEMON 1.2 release to LEMON 1.3 release

What's this?! You postponed this huge task without saying any single word. Could you tell me why?

The attached bundle file​ is good! It contains all the 24 changesets which should be considered related to this ticket (compared to the current main branch). It does not contain the eight changesets from the previous bundle file​, since I reworked them, as I mentioned above (you asked me to do this). What's the problem then? Of course, it would have been better if I had called the file something like 180-all-in-one.bundle.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

milestone changed from LEMON 1.2 release to LEMON 1.3 release

What's this?! You postponed this huge task without saying any single word.

It was certainly not without saying a single word. There was a longish skype conversation before that between... Yes, between you you and me. So, it is pretty much unfair to say it was without a single word.

Could you tell me why?

The attached bundle file​ is good!

Yes, even though there wasn't single word about it, you rightly assume I was not satisfied with that bundle file. :)

I wanted to explain my concerns about it file but you were unwilling to hear my voice. There are quite a few important tasks waiting for me. They alone make my life stressful enough, I'm sorry but I have no time, energy and patience to talk to deaf ears at this time.

Please come up with a clean bundle file and it will soon be merged into the main branch.

Till then, I will not comment (and even try not to read) any response in this ticket. So please do not continue this quarrel here publicly. I guess very few people is interested in it.

[Peter Kovacs]

Replying to alpar:

It was certainly not without saying a single word. There was a longish skype conversation before that between... Yes, between you you and me. So, it is pretty much unfair to say it was without a single word.

Yes, we had a skype conversation, but you said nothing about postponing the ticket. Should I prove it with the skype history? So you certainly did it without saying a single word about it.

On the other hand, the ticket is public, so you should have write a reason here for the publicity, even if you did not want to explain it to me.

Could you tell me why?

The attached bundle file​ is good!

Yes, even though there wasn't single word about it, you rightly assume I was not satisfied with that bundle file. :)

I wanted to explain my concerns about it file but you were unwilling to hear my voice. There are quite a few important tasks waiting for me. They alone make my life stressful enough, I'm sorry but I have no time, energy and patience to talk to deaf ears at this time.

Please come up with a clean bundle file and it will soon be merged into the main branch.

Till then, I will not comment (and even try not to read) any response in this ticket. So please do not continue this quarrel here publicly. I guess very few people is interested in it.

As soon as someone could tell me a real problem with the latest bundle file, I could clarify it. But as far as I know, it is clear. I checked it many times.

By chance, didn't you miss something when you checked the file?

[Peter Kovacs]

I attached two new bundle files.

• 180-new-only-cycle-canceling-6.bundle​
  contains only the 6 new (rebased) patches related to cycle canceling and the reworking of the min cost flow test file. The latest changeset [1d5af6bc963b] requires all the others.
• 180-new-all-in-one-24.bundle​
  contains all the 24 patches that should be considered related to this ticket (just for the sake of convenience).

The changesets could also be revised and pulled using this repository:
​http://lime.cs.elte.hu/~kpeter/hgwebdir.cgi/lemon-candidate/

For the time being, I see now reason to postpone this ticket.

[Alpar Juttner]

Replying to kpeter:

I attached two new bundle files.

• 180-new-only-cycle-canceling-6.bundle​
  contains only the 6 new (rebased) patches related to cycle canceling and the reworking of the min cost flow test file. The latest changeset [1d5af6bc963b] requires all the others.
• 180-new-all-in-one-24.bundle​
  contains all the 24 patches that should be considered related to this ticket (just for the sake of convenience).

As far as I see, these two attachments do not contain anything new or anything different compared to the previous attachments. Or do I miss something?

[Peter Kovacs]

Replying to alpar:

As far as I see, these two attachments do not contain anything new or anything different compared to the previous attachments. Or do I miss something?

From the previous attachments, the 8 changesets of this bundle file​ are obsolete, namely: [0dcf8d92aba8], [7e3516d503c2], [dada1f331b3f], [2c3d5938c03c], [aa1f4ce75b4f], [445a1e99d3db], [ed61814962cc], [71cf7a7747bb].

They are replaced with the 6 changesets of this bundle file​, namely: [8563e7174b43], [88580a216e47], [ad783a4ae986], [904a1ba062b5], [3f0156fe4662], [1d5af6bc963b] (there are less merges among them). So they are the new ones.

The new patches are also involved in this previous bundle​ but along with all other (not obsolete) changesets, which you did not find clean, that's why I created a new file containg only the new changesets. (And an all-in-one bundle for the sake of convenience.)

[Alpar Juttner]

Call me stupid, dull or stubborn or whatever you want but I still claim that the 180-new-all-in-one-24.bundle​ contains nothing new and nothing different compared to the previous attachments:

$ hg clone http://lemon.cs.elte.hu/hg/lemon-main a
requesting all changes
adding changesets
adding manifests
adding file changes
added 785 changesets with 2109 changes to 254 files
updating working directory
208 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg clone a b
updating working directory
208 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg pull -R a 180-cycle-canceling-reworked.bundle 
pulling from 180-cycle-canceling-reworked.bundle
searching for changes
adding changesets
adding manifests
adding file changes
added 24 changesets with 41 changes to 10 files (+1 heads)
(run 'hg heads' to see heads, 'hg merge' to merge)
$ hg pull -R b 180-new-all-in-one-24.bundle 
pulling from 180-new-all-in-one-24.bundle
searching for changes
adding changesets
adding manifests
adding file changes
added 24 changesets with 41 changes to 10 files (+1 heads)
(run 'hg heads' to see heads, 'hg merge' to merge)
$ hg in -R b a
comparing with a
searching for changes
no changes found
$ hg out -R b a
comparing with a
searching for changes
no changes found
changes found

[Peter Kovacs]

Replying to alpar:

Call me stupid, dull or stubborn or whatever you want but I still claim that the 180-new-all-in-one-24.bundle​ contains nothing new and nothing different compared to the previous attachments:

You checked and proved that 180-cycle-canceling-reworked.bundle​ and 180-new-all-in-one-24.bundle​ are identical. That is exactly what I stated. Both are good, both are clean.

Note that neither of these files contains the obsolete changesets from 180-cycle-canceling.bundle​, which form another branch from [0dcf8d92aba8] to [71cf7a7747bb]. If you are looking for differences, you should have compared the latest three bundle files to this obsolete file. Otherwise you will certainly not find any differences.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

Call me stupid, dull or stubborn or whatever you want but I still claim that the 180-new-all-in-one-24.bundle​ contains nothing new and nothing different compared to the previous attachments:

You checked and proved that 180-cycle-canceling-reworked.bundle​ and 180-new-all-in-one-24.bundle​ are identical. That is exactly what I stated.

Then, I can't understand the purpose of 25. It certainly doesn't bring finishing the ticket closer. What did you expect from reattaching an already attached bundle file with a different name?

[Alpar Juttner]

Replying to alpar:

What did you expect from reattaching an already attached bundle file with a different name?

Oh no, I'm sorry. Please do not answer this. Please!

[Peter Kovacs]

Replying to kpeter:

As soon as someone could tell me a real problem with the latest bundle file, I could clarify it. But as far as I know, it is clear. I checked it many times.

Finally, it turned out in a personal conversation that Alpar's displeasure is not related to the new changesets of the last week, it is about some merges among the oldest patches that could be avoided if the changesets are rebased.

Therefore, I rebased and reorganized all patches related to this task. So please forget all attachments except for the last file: 180-all-changesets-reworked.bundle​. It contains only 17 changesets on the top of the current main repository without any merges. The latest 2 changesets are entirely new ([7d1310c3fd0c] and [e76d9f48a4bf]), they contain small fixes. The other 15 changesets are the reorganized and reworked versions of former patches in this ticket.

For a simpler overview you can click here:
​http://lime.cs.elte.hu/~kpeter/hgwebdir.cgi/lemon-candidate/graph/808?revcount=16

I do hope I could clarify everything here.

[Peter Kovacs]

I reviewed this ticket. I made a follow-up ticket, see #328. Apart from that, I see only two tasks/questions left here. The others are no longer relevant or not so important.

• Please review the changesets (in their latest versions), especially those parts of the algorithm interfaces and documentations that are different form NetworkSimplex. Namely the run() functions and the named parameters of the three new classes.

• What do you think about this idea from comment 14:

Considering the above experiments, it would be worth to test such ideas for the maximum flow algorithms, as well. E.g., could Preflow be made faster using an efficient data structure for the residual network? I guess that it is possible for large and difficult instances. However, I actually don't think that Preflow or Circulation should copy the digraph (and its maps), but could we draft a good guideline for this question? Which algorithms are allowed/welcomed to copy the graph (and some maps on it)?

[Alpar Juttner]

Replying to kpeter:

I'm about to merge the latest bundle file into the main branch. However Valgrind reports error in min_cost_flow_test. Could you please investigate the reason?

(At the base of the changesets the valgrind support does not exists. Thus I suggest cloning the main, pulling the bundle file, hg update-ing to the tip of the current main, then merging each changesets one-by-one to the tip (hg merge -r rev) and check them).

[Peter Kovacs]

Replying to alpar:

I'm about to merge the latest bundle file into the main branch.

Thank you.

However Valgrind reports error in min_cost_flow_test. Could you please investigate the reason?

I will check it soon.

[Peter Kovacs]

Replying to alpar:

However Valgrind reports error in min_cost_flow_test. Could you please investigate the reason?

The error was in BellmanFord, it contained a foul memory leak bug. See #51 for a bugfix. However, I don't want to rebase these changesets, so please merge them with the bugfix.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

However Valgrind reports error in min_cost_flow_test. Could you please investigate the reason?

The error was in BellmanFord, it contained a foul memory leak bug. See #51 for a bugfix.

I like Valgrind.

However, I don't want to rebase these changesets,

I did it for you, see the line of changeset from [d3e32a777d0b] to [072ec8120958]. I have also fixed an uninitialized variable warning in one of the changesets.

Btw., have you heard about hg rebase? It makes rebasing a breeze.