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

[Kovács Péter]

Dear All,

I also checked this problem.

   1. DIMACS reader: our implementation uses the standard C++ operator 
 >> to read numbers. In case of -9.03353e+06 and integer value type, it 
reads -9 (and the reader simply skips the remainder of the line). So a 
feasible problem instance with supply/demand only 9 is read.

   2. Integer types: NS also works correctly with int and long long 
arithmetic for this instance if you properly transform the input file. 
Not only the supply/demand values are given in floating point format, 
but there are a lot of arcs with the same capacity. So be sure to 
replace all the 8181 occurances of 9.03353e+06 to 9033530. For this 
modified file, I got the following results:

   NetworkSimplex<GR, int>	 194s  (default for dimacs_solver)
   NetworkSimplex<GR, long long>	 200s  (-long option)
   NetworkSimplex<GR, double>     221s  (-double option)

All the three versions yield the same total cost (847714917290).

   3. Performance: Matt, we would be pleased if you could send us all 
your comparison results. I'm really intrested in it! Currently, I don't 
know the reasons of the worse running time on this input, but it is 
surely not an abnormal behaviour. Using other pivot rules or disabling 
heuristics even slightly worsens the running time. Our other fast solver 
(CostScaling) also runs slower on this instance (298s). According to the 
structure of the input file, I guess that this is a special hard min 
cost instance. It is probably created with the GOTO network generator 
(or something similar). If other (primal) NS implementations perform 
much better on this instance, than they probably know a heuristic that I 
don't. :(

   4. User/system time: I have no idea for the reasons of Alpar's 
problem. On the machines I checked, the results were normal.

Best regards,
Peter


> 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
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user