[Lemon-devel] Regarding the implementation of Cancel & Tighten

[Paul Swoboda]

Dear developers,

I have lately been interested in cancel and tighten algorithms for 
minimum cost network flow problems. I have checked your implementation 
as well as the benchmark paper "An Experimental Study of Minimum Cost 
Flow Algorithms" by Zoltán Királya and Péter Kovács, where cancel and 
tighten did not fare very favourably, compared to network simplex and 
cost scaling algorithms. After looking into the source code, it seems 
that starting at line 987 in cycle_cancelling.h, version lemon-1.2.3, 
you do not use dynamic trees for canceling cycles as proposed in 
"Finding Minimum-Cost Circulations by Canceling Negative Cycles" by 
Goldberg and Tarjan. Is there a specific reason for this? I would be 
very interested in the possibility to accelerate the algorithm in practice.

Best regards,

Paul Swoboda