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

[Alpár Jüttner]

Hi,

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.

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.

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

Regards,
Alpar


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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: mixopt.patch
Type: text/x-patch
Size: 1006 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100817/a8b597aa/attachment.patch>