Use HartmannOrlinMmc instead of HowardMmc in CycleCanceling

[Peter Kovacs]

The min cost flow algorithms implemented in CycleCanceling are rather slow in practice, their only advantage is that two of them is proved to be strongly polynomial if the applied min mean cycle algorithm is also strongly polynomial. Although HowardMmc is clearly faster than HartmannOrlinMmc in practice, its theoretical running time is not polynomial. I think it is more important to ensure that these implementations are indeed strongly polynomial than using Howard's min mean cycle algorithm for efficiency reasons.

Actually, the current state of the library is not consistent. The doc says that two cycle canceling implementations are strongly polynomial and expresses their theoretical running time, while the implementation uses Howard's algorithm, so it is _not_ polynomial. I'm sorry for introducing such an inconsistency.

Therefore, I suggest to use HartmannOrlinMmc in the cycle canceling implementations.

[Peter Kovacs]

[6422da4647f2] contains the suggested modification.

Note that it makes the Minimum Mean Cycle Canceling and the Cancel-And-Tighten algorithms much slower in order to ensure strongly polynomial time bound. In the future, it would be nice to implement such a min mean cycle algorithm, that is competitive with Howard's algorithm in practice, but runs in strongly polynomial time. Such an implementation could replace the Hartmann-Orlin algorithm in cycle-canceling methods. (However, cycle canceling methods are orders of magnitude slower than other min cost flow algorithms indenendetly of this choice.)

[Peter Kovacs]

[6422da4647f2] is based on an old changeset [d3ea191c3412], so it can be merged to release branches, as well.

[Alpar Juttner]

Replying to kpeter:

(However, cycle canceling methods are orders of magnitude slower than other min cost flow algorithms indenendetly of this choice.)

Are you sure cycle canceling has no practical use at all? I'm thinking about a situation when you have a close to optimal feasible flow in advanve. For example you know the optimal solution to a problem instance, but then you change the cost of some edges, so you want to augment the solution. Can't cycle canceling be a good choice in this case?

[Peter Kovacs]

Replying to alpar:

Replying to kpeter:

(However, cycle canceling methods are orders of magnitude slower than other min cost flow algorithms indenendetly of this choice.)

Are you sure cycle canceling has no practical use at all?

No, I'm not sure. That's why I still maintain them despite their poor performance in all test cases I considered so far. :)

I'm thinking about a situation when you have a close to optimal feasible flow in advanve. For example you know the optimal solution to a problem instance, but then you change the cost of some edges, so you want to augment the solution. Can't cycle canceling be a good choice in this case?

In such cases, cycle-canceling methods would probably be efficient, but other algorithms, e.g. network simplex, would also be quite fast. Actually, I haven't considered such use cases (cost reoptimization) yet, so I don't know how the implemented algorithms would perform. However, I think network simplex and cost scaling would be superior to cycle-canceling methods even in these cases.

There are some papers that study these use cases, but I don't know experiments with cycle-canceling methods. For example, this paper provides a recent study of cost reoptimization: ​http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7741

[Peter Kovacs]

I have another idea to solve this issue. Howard's algorithm performs simple, linear time iterations, but polynomial time limits are not known for the number of iterations. However, it usually finds the optimal solution after only a few iterations (compared to the other two algorithms). So, it would be quite easy to introduce an optional limit for the number of iterations in the implementation of Howard's algorithm and the client code can switch to a polynomial algorithm, e.g. Hartmann-Orlin if Howard's algorithm does not find the optimal solution in e.g. O(n) iterations.

What do you think about such a modification of the cycle-canceling methods? This would ensure the strongly polynomial running time, but the practical running time would be (roughly) the same as in the current release.

[Peter Kovacs]

[81d7e0a1b09d] contains an implementation of the last proposal.

According to my tests, the number of iterations in Howard's algorithm never exceeded 0.1*n and as the graph gets bigger, this ratio (max number of iterations divided by the number of nodes) becomes smaller. Therefore, setting the iteration limit to 0.25*n seemed to be a rational choice. If this limit is exceeded, the Hartmann-Orlin is executed instead of Howard. Experimental tests show indentical running time to the the current version, but the documented theoretical running time is now ensured since Howard's algorithm performs a single iteration in O(n+m) time.

[Peter Kovacs]

[c63fed6750c6] is a slightly modified version of the proposed solution. The iteration limit is now set to n instead of n/4. It seems to be "safer" for small graphs.

This patch is made on the top of [ee2fe24de015], see #438.

[Peter Kovacs]

I attached a new variant of this patch [35d42156b178] by rebasing it on the top of [6d5d77e50d4b], see #438.

[Peter Kovacs]

The previously cited patch was wrong (I accidentally reverted some recent changes).

The final version is now attached, it is [f6f6896a4724], which is based on [21a9f829ab68] from #438.

[Alpar Juttner]

I think, the fact that an algorithm is strongly polynomial is of little importance when it comes to practical use.

As a general policy, algorithms should be implemented in a way provides the best practical performance.

The best solution would probably be to let the user decide on which mean cycle algorithm (s)he wants to use, with a default setting to that of best practical performance.

Otherwise, the idea in comment above is nice, for it is both fast and robust.

If we want to give more freedom to the user, we could allow setting the iteration limit. Thus limit=0 would mean that Hartmann-Orlin is used entirely, while limit=infinite would result in using Howard. The default value would be the mixed version Peter proposed above.

[Peter Kovacs]

I agree. In case of these cycle-canceling algorithms, however, I find it beneficial to ensure strongly polynomial running time, since they are primarly known because of this property and the proposed solution does not worsen their practical performance.

Otherwise, the idea in comment above is nice, for it is both fast and robust. If we want to give more freedom to the user, we could allow setting the iteration limit. Thus limit=0 would mean that Hartmann-Orlin is used entirely, while limit=infinite would result in using Howard. The default value would be the mixed version Peter proposed above.

Yes, it would be possible, but I don't find it so important. There are many other parameters/options of different min cost flow algorithms that are not customizable, although they could also be interesting.

Currently, I would prefer applying the attached patch only, but I'm open for such an extension if it turns out to be practical.

[Alpar Juttner]

[f6f6896a4724] is merged to the main branch.