COIN-OR::LEMON - Graph Library

Opened 8 years ago

Closed 7 years ago

#436 closed enhancement (fixed)

Use HartmannOrlinMmc instead of HowardMmc in CycleCanceling

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.3 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

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.

Attachments (4)

436-6422da4647f2.patch (1.4 KB) - added by Peter Kovacs 8 years ago.
436-81d7e0a1b09d-cc-str-poly.patch (4.7 KB) - added by Peter Kovacs 8 years ago.
436-c63fed6750c6-cc-str-poly.patch (4.7 KB) - added by Peter Kovacs 8 years ago.
436-new-f6f6896a4724.patch (4.8 KB) - added by Peter Kovacs 7 years ago.

Download all attachments as: .zip

Change History (17)

Changed 8 years ago by Peter Kovacs

Attachment: 436-6422da4647f2.patch added

comment:1 Changed 8 years ago by Peter Kovacs

Owner: changed from Alpar Juttner to Peter Kovacs
Status: newassigned

[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.)

comment:2 Changed 8 years ago by Peter Kovacs

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

comment:3 in reply to:  1 ; Changed 8 years ago by 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?

comment:4 in reply to:  3 Changed 8 years ago by 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

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

Changed 8 years ago by Peter Kovacs

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

Changed 8 years ago by Peter Kovacs

comment:7 Changed 8 years ago by 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.

comment:8 Changed 7 years ago by Peter Kovacs

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

Changed 7 years ago by Peter Kovacs

Attachment: 436-new-f6f6896a4724.patch added

comment:9 Changed 7 years ago by 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.

comment:10 Changed 7 years ago by 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.

comment:11 Changed 7 years ago by 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.

comment:12 Changed 7 years ago by Alpar Juttner

Type: defectenhancement

comment:13 Changed 7 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

[f6f6896a4724] is merged to the main branch.

Note: See TracTickets for help on using tickets.