[Lemon-devel] [Lemon-user] performance of network simplex on instance i_n13
Kovács Péter
kpeter at inf.elte.hu
Mon Aug 23 00:28:39 CEST 2010
Hi All,
I made remarkable improvements in the performance of NS with arc mixing.
According to the benchmark tests of this new version and considering
Alpar's reasons and the experiments with the input sent by Matthew, I
suggest to use arc mixing by default.
For more details, see
http://lemon.cs.elte.hu/trac/lemon/ticket/391#comment:2
Regards,
Peter
2010.08.18. 13:37 keltezéssel, Alpár Jüttner írta:
> Hi,
>
>> Alpar, thanks for this idea and the patch!
>
> Shall we incorporate this path to the main branch?
>
> Regards,
> Alpar
>
>> 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
>>>
>>
>
>
>
More information about the Lemon-devel
mailing list