[Lemon-user] performance of network simplex on instance i_n13

[Alpár Jüttner]

Hi,
> 
> I've put the dimacs form of the problem here:
>     http://coral.ie.lehigh.edu/~magh/tmp/i_n13.dimacs

I'm puzzled by this for several reasons.

On my laptop I get this results:

        $ ./tools/dimacs-solver -double i_n13.dimacs.int
        Problem type: min
        Num of nodes: 8181
        Num of arcs:  739733
        
        Sum of supply values: 0
        GEQ supply contraints are used for NetworkSimplex
        
        Read the file: u: 1.77s, s: 0.07s, cu: 0s, cs: 0s, real: 1.86615s
        Setup NetworkSimplex class: u: 0.05s, s: 0.04s, cu: 0s, cs: 0s, real: 0.092091s
        Run NetworkSimplex: u: 3.46s, s: 242.48s, cu: 0s, cs: 0s, real: 247.726s
        
        Feasible flow: found
        Min flow cost: 8.47715e+11

It is 247, but only 3.4s in the userspace??? First I said, no, the user
and system times must have been changed. But I checked the related code
and couldn't find any bug.

Secondly, if I use -int or -long, it runs basically in 0s and gives a
feasible solution, but a wrong one (Min flow cost: 137). I guess, the
reason is that the demand is given in a floating point form (9.03353e
+06). I would at least expect a format error message in this case.

Thirdly, I replaced the demand to integer format (9033530), and rerun
"./dimacs-solver -long". It says: "Feasible flow: not found". Why?


Regards,
Alpar