[Lemon-user] problem with NetworkSimplex

[Kovács Péter]

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'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.

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

Best regards,
Peter