[Lemon-user] big1.net optimal flow not matching LP solvers

[Alpár Jüttner]

On Mon, 2010-02-15 at 20:55 -0500, Matthew Galati wrote:
> Hi. I tried using the dimacs-solver on big1.net from:
>   http://ftp.zib.de/pub/mp-testdata/mincost/netg/index.html
> 
> The LEMON solution states MinFlowCost: 506,515,059.
> 
> However, when I formulate this as a linear program and solve with an
> LP solver, I get:  3.48662534E+10.
> 
> I also checked with Cplex (which has a Dimacs parser) and it also got
> 3.48662534E+10 as the optimal flow.
> 
> Is this a bug?

No, it isn't. It is an integer overflow problem. 3.48E+10 simply does
not fit into the 'int' data type, which is used by default in the LEMON
solver. Change it to 'long long' and you will get the right result:

$ ./dimacs-solver -long big1.net 
Problem type: min
Num of nodes: 25000
Num of arcs:  120000
[...]
Feasible flow: found
Min flow cost: 34866253427

You can also use 'double' or 'long double' (with options '-double' and
'-ldouble', resp.), but floating point arithmetic may suffer from
numerical errors in some cases, of course.

Regards,
Alpar

> 
> Thanks,
> Matt
> 
> 
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user