[Lemon-user] problem with NetworkSimplex

[Leandro Callegari Coelho]

On 12-03-13 6:57 PM, Kovács Péter wrote:
> Hi,
>
>> Dear all,
>>
>> I have just started using LEMON to solve min cost flow problems, which
>> have their costs/flows/supplies modified iteratively. As an example, one
>> of the graphs has less than 30 nodes and is solved in a fraction of a
>> second. However, from time to time the /.run/ function keeps running for
>> several seconds until I decide to quit.
>
> NetworkSimplex is typically quite efficient and robust, but different 
> problem instances of (roughly) the same size may require rather 
> different running time to solve. However, NetworkSimplex must 
> definitely terminate in a finite number of iterations if all input 
> data are integer-valued.
>
>> Since everything else seemed OK, I decided to change the solver to
>> /CostScaling/ and the problem disappeared.
>
> Another reason why it is beneficial that LEMON provides more 
> algorithms for solving the same problem. :)
I completely agree!
>
>> I'd be glad if someone helped me investigate this problem and I'm ready
>> to provide working examples of this crash if someone can tell me the
>> piece of code to add just before invoking
>>
>> /graph.lowerMap(lowerMap).upperMap(upperMap).costMap(costMap).supplyMap(supplyMap).run();/ 
>>
> >
> > in order to save the incumbent graph to the disc so that I can show
> > it to you.
>
> Thank you for your cooperation. Try this piece of code that uses the 
> DigraphWriter utility to print your network to the standard output in 
> LEMON's graph format (LGF).
>
>   digraphWriter(g, std::cout)
>     .arcMap("lower", lowerMap)
>     .arcMap("upper", upperMap)
>     .arcMap("cost", costMap)
>     .nodeMap("supply", supplyMap)
>     .run();
>
> If you would like to write the output directly to a file, you can also 
> pass a file name or any std::ostream to digraphWriter() instead of 
> std::cout. I will check the problem if you send this output to me.
I will save some graphs tomorrow and will forward them directly to your 
email. Thanks!
>
>> If it helps you narrow the problem: Lemon v. 1.2.3, all maps are integer
>> except for the costMap which is defined as double like this:
>>
>> ///NetworkSimplex<ListDigraph, int, double> graph(g);
>> CostScaling<ListDigraph, int, double> graph(g);/
>
> What about the cost values? Are they integer-valued or not?
> Note that the current implementations of minimum-cost flow algorithms 
> in LEMON are intended to be used only with integer costs, while the 
> number type can be double. (Actually, CapacityScaling is an exception, 
> as it is stable for arbitrary real-valued arc costs, although this 
> fact is only indicated in the latest development version yet.)
Cost values are doubles... it was my fault, I thought I could change the 
type and everything would be OK. It seems to be working now with the 
CostScaling algorithm for me, but it is good to know that it might not 
be safe. I hope the CapacityScaling algorithm will not perform much 
worse than the other algorithms.
>
> Best regards,
> Peter