[Lemon-user] Lemon Cycle canceling

[Kovács Péter]

Hi,

> I'm using your library to implement a new cycle canceling algorithm.
> I'm trying to figure out why the number of nodes in the residual network
> is ( n + 1 ).

LEMON implements algorithms for solving a general form of the min cost 
flow problem, in which inequality constraints are allowed (although 
typical definitions of this problem contain equality constraints). For 
the details, see:
http://lemon.cs.elte.hu/pub/doc/1.2.3/a00005.html

To handle this generality, an additional root node is added to the 
underlying graph as well as arcs connecting this root node to each 
oiriginal node (these arcs represent LP slack variables corresponding to 
the supply/demand constraints).

> Also, are you aware that the solution to the circulation algorithm does
> not provide an admissible primal form solution.  meaning that for
> instance in your min_cost_flow_test instance, the solution given
> initially contains a cycle  2-> 10 -> 4 -> 0  and 2 -> 0.  All of these
> arcs have  > 0 and < u flow.  At least one of them should however be at
> 0 or U by modifying the cycle flow by some delta unit.

Yes. Circulation algorithm does not ensure that the returned solution is 
admissible in this sense (i.e. basic). There is a related feature 
request here:
http://lemon.cs.elte.hu/trac/lemon/ticket/216

Moreover, the min cost flow algorithms can also return a non-basic 
solution (in case of cycles with zero total cost) except for NetworkSimplex.

Best regards,
Peter