LEMON: Ticket #436: Use HartmannOrlinMmc instead of HowardMmc in CycleCanceling
https://lemon.cs.elte.hu/trac/lemon/ticket/436
<p>
The min cost flow algorithms implemented in <code>CycleCanceling</code> 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 <code>HowardMmc</code> is clearly faster than <code>HartmannOrlinMmc</code> 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.
</p>
<p>
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.
</p>
<p>
Therefore, I suggest to use <code>HartmannOrlinMmc</code> in the cycle canceling implementations.
</p>
en-usLEMONhttps://lemon.cs.elte.hu/trac/lemon/chrome/site/lemon-logo.gif
https://lemon.cs.elte.hu/trac/lemon/ticket/436
Trac 1.2.3Peter KovacsMon, 30 Jan 2012 20:57:08 GMTattachment set
https://lemon.cs.elte.hu/trac/lemon/ticket/436
https://lemon.cs.elte.hu/trac/lemon/ticket/436
<ul>
<li><strong>attachment</strong>
set to <em>436-6422da4647f2.patch</em>
</li>
</ul>
TicketPeter KovacsMon, 30 Jan 2012 21:05:59 GMTowner, status changed
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:1
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:1
<ul>
<li><strong>owner</strong>
changed from <em>Alpar Juttner</em> to <em>Peter Kovacs</em>
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>assigned</em>
</li>
</ul>
<p>
<a class="missing changeset" title="No changeset 6422da4647f2 in the repository">[6422da4647f2]</a> contains the suggested modification.
</p>
<p>
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.)
</p>
TicketPeter KovacsMon, 30 Jan 2012 21:08:32 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:2
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:2
<p>
<a class="missing changeset" title="No changeset 6422da4647f2 in the repository">[6422da4647f2]</a> is based on an old changeset <a class="changeset" href="https://lemon.cs.elte.hu/trac/lemon/changeset/d3ea191c3412/lemon" title="Rename min mean cycle classes and their members (#179)
with respect to ...">[d3ea191c3412]</a>, so it can be merged to release branches, as well.
</p>
TicketAlpar JuttnerFri, 03 Feb 2012 05:08:00 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:3
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:3
<p>
Replying to <a class="ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:1" title="Comment 1">kpeter</a>:
</p>
<blockquote class="citation">
<p>
(However, cycle canceling methods are orders of magnitude slower than other min cost flow algorithms indenendetly of this choice.)
</p>
</blockquote>
<p>
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?
</p>
TicketPeter KovacsFri, 03 Feb 2012 13:32:39 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:4
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:4
<p>
Replying to <a class="ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:3" title="Comment 3">alpar</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:1" title="Comment 1">kpeter</a>:
</p>
<blockquote class="citation">
<p>
(However, cycle canceling methods are orders of magnitude slower than other min cost flow algorithms indenendetly of this choice.)
</p>
</blockquote>
<p>
Are you sure cycle canceling has no practical use at all?
</p>
</blockquote>
<p>
No, I'm not sure. That's why I still maintain them despite their poor performance in all test cases I considered so far. :)
</p>
<blockquote class="citation">
<p>
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?
</p>
</blockquote>
<p>
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.
</p>
<p>
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: <a class="ext-link" href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7741"><span class="icon"></span>http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7741</a>
</p>
TicketPeter KovacsFri, 03 Feb 2012 13:40:19 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:5
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:5
<p>
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.
</p>
<p>
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.
</p>
TicketPeter KovacsFri, 03 Feb 2012 18:14:29 GMTattachment set
https://lemon.cs.elte.hu/trac/lemon/ticket/436
https://lemon.cs.elte.hu/trac/lemon/ticket/436
<ul>
<li><strong>attachment</strong>
set to <em>436-81d7e0a1b09d-cc-str-poly.patch</em>
</li>
</ul>
TicketPeter KovacsFri, 03 Feb 2012 18:23:12 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:6
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:6
<p>
<a class="missing changeset" title="No changeset 81d7e0a1b09d in the repository">[81d7e0a1b09d]</a> contains an implementation of the last proposal.
</p>
<p>
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.
</p>
TicketPeter KovacsWed, 15 Feb 2012 15:22:37 GMTattachment set
https://lemon.cs.elte.hu/trac/lemon/ticket/436
https://lemon.cs.elte.hu/trac/lemon/ticket/436
<ul>
<li><strong>attachment</strong>
set to <em>436-c63fed6750c6-cc-str-poly.patch</em>
</li>
</ul>
TicketPeter KovacsWed, 15 Feb 2012 15:25:31 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:7
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:7
<p>
<a class="missing changeset" title="No changeset c63fed6750c6 in the repository">[c63fed6750c6]</a> 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.
</p>
<p>
This patch is made on the top of <a class="missing changeset" title="No changeset ee2fe24de015 in the repository">[ee2fe24de015]</a>, see <a class="closed ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/438" title="#438: enhancement: Optional iteration limit in HowardMmc (closed: fixed)">#438</a>.
</p>
TicketPeter KovacsThu, 15 Nov 2012 01:03:00 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:8
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:8
<p>
I attached a new variant of this patch <a class="missing changeset" title="No changeset 35d42156b178 in the repository">[35d42156b178]</a> by rebasing it on the top of <a class="missing changeset" title="No changeset 6d5d77e50d4b in the repository">[6d5d77e50d4b]</a>, see <a class="closed ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/438" title="#438: enhancement: Optional iteration limit in HowardMmc (closed: fixed)">#438</a>.
</p>
TicketPeter KovacsThu, 15 Nov 2012 06:20:54 GMTattachment set
https://lemon.cs.elte.hu/trac/lemon/ticket/436
https://lemon.cs.elte.hu/trac/lemon/ticket/436
<ul>
<li><strong>attachment</strong>
set to <em>436-new-f6f6896a4724.patch</em>
</li>
</ul>
TicketPeter KovacsThu, 15 Nov 2012 06:24:38 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:9
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:9
<p>
The previously cited patch was wrong (I accidentally reverted some recent changes).
</p>
<p>
The final version is now attached, it is <a class="changeset" href="https://lemon.cs.elte.hu/trac/lemon/changeset/f6f6896a4724/lemon" title="Ensure strongly polynomial running time for CycleCanceling (#436)
The ...">[f6f6896a4724]</a>, which is based on <a class="changeset" href="https://lemon.cs.elte.hu/trac/lemon/changeset/21a9f829ab68/lemon" title="Optional iteration limit in HowardMmc (#438)">[21a9f829ab68]</a> from <a class="closed ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/438" title="#438: enhancement: Optional iteration limit in HowardMmc (closed: fixed)">#438</a>.
</p>
TicketAlpar JuttnerThu, 15 Nov 2012 08:15:46 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:10
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:10
<p>
I think, the fact that an algorithm is strongly polynomial is of little importance when it comes to practical use.
</p>
<p>
As a general policy, algorithms should be implemented in a way provides the best <em>practical</em> performance.
</p>
<p>
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.
</p>
<p>
Otherwise, the idea in <a class="ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:6" title="Comment 6">comment above</a> is nice, for it is both fast and robust.
</p>
<p>
If we want to give more freedom to the user, we could allow setting the iteration limit. Thus limit=0 would mean that <code>Hartmann-Orlin</code> is used entirely, while limit=infinite would result in using <code>Howard</code>. The default value would be the mixed version Peter proposed above.
</p>
TicketPeter KovacsWed, 21 Nov 2012 06:52:38 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:11
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:11
<p>
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.
</p>
<blockquote class="citation">
<p>
Otherwise, the idea in <a class="ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:6" title="Comment 6">comment above</a> 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 <code>Hartmann-Orlin</code> is used entirely, while limit=infinite would result in using <code>Howard</code>. The default value would be the mixed version Peter proposed above.
</p>
</blockquote>
<p>
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.
</p>
<p>
Currently, I would prefer applying the attached patch only, but I'm open for such an extension if it turns out to be practical.
</p>
TicketAlpar JuttnerFri, 22 Feb 2013 08:09:30 GMTtype changed
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:12
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:12
<ul>
<li><strong>type</strong>
changed from <em>defect</em> to <em>enhancement</em>
</li>
</ul>
TicketAlpar JuttnerFri, 22 Feb 2013 13:18:55 GMTstatus changed; resolution set
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:13
https://lemon.cs.elte.hu/trac/lemon/ticket/436#comment:13
<ul>
<li><strong>status</strong>
changed from <em>assigned</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
<a class="changeset" href="https://lemon.cs.elte.hu/trac/lemon/changeset/f6f6896a4724/lemon" title="Ensure strongly polynomial running time for CycleCanceling (#436)
The ...">[f6f6896a4724]</a> is merged to the main branch.
</p>
Ticket