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

[Kovács Péter]

Hi,

Alpar, thanks for this idea and the patch! I did not think of the arc 
mixing option.

> The constructor of the NetworkSimplex class has a second parameter that
> allows mixing the order of the graph edges. This feature is switches off
> by default. If you want to play with this feature, please find the
> attached patch; it adds a -mix option to dimacs-solver.
>
> I tested this on your input file and it improves the running time by a
> factor of 3.6 (from 250s to 69s). I'm curious to hear your experience
> with using this feature.

Strange. We have not expected such a big difference before. I'm also 
curious about your experiments. Does our NS perfom competitively with 
arc mixing? Does this option make NS faster on all instances you tested?

> Although NS is very fast in practice, it is in theory of exponential
> running time. We have even noticed once in the past that its running
> time may be very sensitive to the order of the edges (i.e. to the way
> how we list them). We saw an example where simply reversing the order
> caused an over 2x running time difference. That's why we implemented the
> 'arc_mixing' option which performs a simple randomization of the edge
> order, therefore it eliminates the bad coincidences in the network
> descriptions in most cases.
 >
> For most of the well-known test instances, this option alters the
> running time only by a little, but again, there are instances on which
> it improves a _lot_. I don't recall any instances on which it caused big
> worsening, Peter may fix me if I'm wrong.

Yes, NS is sensitive for the order of the arcs. For most of the 
generated and real-life problem instances, the original arc order (which 
is usually a kind of "natural" order) turned out to be significantly 
better (often by a factor of 1.5-2!) according to my tests. I also found 
instances for which mixing helped, but I did not measure a ratio larger 
than 1.5, and these instances were typically simple. Mixing could make 
NS more robust by eliminating bad coincidences but it also eliminates 
the good coincidences.

> I have always wanted this option to be the default as it makes our NS
> implementation more robust. I had a rather long debate on this topic
> with Peter, but I lost it.  His argument was that _on the average_
 > 'arc_mixing' makes the performance a bit worse (I don't remember the
 > exact numbers).

I think, the debate wasn't too long or hard. It was mainly about 
introducing the user option (which was more important), and we agreed in 
it. At the end, I wrote: "It is not clear which one is better, but I 
slightly prefer not to randomize the arcs as a default behavior" and 
Alpar accepted it. (See http://lemon.cs.elte.hu/trac/lemon/ticket/298 
for the details.)

Such a decision is not so easy to make, since there is no absolute 
winner. Maybe I was wrong, but my suggestion was based on comprehensive 
benchmark tests. In fact, I could accept the change of the default option.

Regards,
Peter


> On Mon, 2010-08-16 at 19:54 +0200, Alpár Jüttner wrote:
>> 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
>