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

[Alpár Jüttner]

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
> >
>