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

[Alpár Jüttner]

On Mon, 2010-08-16 at 11:20 -0400, Matthew Galati wrote:
> 
> 
>                $ ./tools/dimacs-solver -double i_n13.dimacs.int
>                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.
>         
> 
> On my machine (linux/g++), user time matches real time for this
> instance. This is giving the correct solution - and seems to take long
> (relative to other solvers).
> 
I have checked it on another machine and it reports

Run NetworkSimplex: u: 230.57s, s: 0.21s, cu: 0s, cs: 0s, real: 230.749s

which is reasonable (though it is still too slow). But I'm still curious
about the reason for the suspicious results on my laptop. Especially
because I plan to upgrade our server to the same system (Opensuse 11.3)

>         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.
> 
> I don't think the reader checks for this - so it is probably just
> treating it as int or long and truncating - causing the wrong
> objective.

You are probably wright, but either
      * should interpret 9.03353e+06 as 9033530 or
      * should exit with an error message.
> 
>         Thirdly, I replaced the demand to integer format (9033530),
>         and rerun
>         "./dimacs-solver -long". It says: "Feasible flow: not found".
>         Why?

> My guess would be an overflow here.
> 
I don't know. The numbers in the input doesn't seem that big.

Regards,
Alpar