[Symphony] Dramatic performance drop since 5.1.10

[Ted Ralphs]

Well, it's a hack mainly because we should have a parameter for it :).
Yes, you are right, it is difficult to know a priori whether primal or
dual will work better. At the moment, it seems that dual is a better
default choice in the absence of any other information. In 5.1, we
always used dual. I'm not sure why that was changed. We need look into
that.

Of course, once you start adding cuts, then dual is the sensible
choice. We do not support barrier because this would require a whole
host of changes related to the lack of warm starting methods in that
case, the need to do a crossover step to get a basis, etc. Much of the
implementation assumes that there is warm starting and that the LP
solver produces a basis. In general, barrier is probably only going to
be a good choice for branch and cut in very isolated cases where the
difference in solution times for the LP relaxations is enough to
overcome the penalty paid by the lack of warm start.

Cheers,

Ted

On Fri, Sep 11, 2009 at 10:12 PM, claude philippe medard
<claude.philippe.medard at gmail.com> wrote:
> One comment about (2): i would not coin it an ugly hack. it is always very
> difficult to know before hand whether dual or primal simplex is faster on
> some LPs, in fact this is true for any solver (cplex, xpress, ...) What lp
> solver does 5.1.10 use initially, is it dual simplex as well ?
>
> as a side comment: does symphony support barrier as well ? on instances with
>>=50K constraints and 100K variables, cplex barrier is extremely faster
> (2mns) than its primal simplex (20 mns) or dual simplex (10mns). It is the
> same with Xpress. just so you know.
>
> best regards,
> Claude Ph Medard
>
> On Fri, Sep 11, 2009 at 6:50 PM, Ashutosh Mahajan <asm4 at lehigh.edu> wrote:
>>
>> Dear Pierre Le Bodic
>>
>> i think you can speed up your symphony for your instances by doing these 2
>> things.
>>
>> 1. set your parameter or option file to contain
>> fp_enabled -1
>> prep_level  0
>> this will disable feasibility pump and presolve. presolve takes >20s on
>> some
>> instances.
>>
>> 2. you will have to edit SYMPHONY/src/LP/lp_genfunc.c and change line 275
>> from
>>         termcode = initial_lp_solve(lp_data, &iterd);
>>   to
>>         termcode = dual_simplex(lp_data, &iterd);
>>
>> the LP relaxation of your instances seem to get solved much faster by
>> dual_simplex than by initial_lp_solve.
>>
>> im sorry about the fact that 1. is not documented yet and 2. is an ugly
>> hack.
>> hope this cuts down the time to something acceptable. thanks for sending
>> your
>> instances. its really helps to see that a solver 'tuned' towards
>> benchmark instances can become significantly slower on others.
>>
>> we will try to fix the above issues in trunk soon.
>>
>> ashutosh
>>
>>
>>
>> On Thu, 10 Sep 2009, Ted Ralphs wrote:
>>
>> > This is unfortunate, but not actually too surprising. In 5.2, we added
>> > features that were focused on solving the more difficult instances and
>> > tuned our parameters to improve speed on those instances, but probably
>> > neglected to ensure that performance on easier instances was not too
>> > degraded. Thanks for the reminder :). What frequently happens when you
>> > do parameter tuning on larger instances is that smaller instances
>> > actually get slower as an unintended consequence. It's a difficult
>> > balance to strike. Let us look at these and see if we can come up with
>> > a better balance of improving performance on large instances without
>> > degrading performance on smaller instances. In any case, it should be
>> > relatively easy to replicate the performance of 5.1 with customized
>> > parameter settings.
>> >
>> > Chers,
>> >
>> > Ted
>> >
>> > On Thu, Sep 10, 2009 at 5:11 AM,  <Pierre.Lebodic at lri.fr> wrote:
>> > > Hello,
>> > >
>> > > I've been using the C callbacks of Symphony 5.1.10 for a while and I
>> > > recently tried updating to 5.2. On a batch of 80 test instances, I
>> > > measured the run time of the updated solver. "Sys time" went from 2sec
>> > > with 5.1 to 2m55sec with 5.2. As a comparison, cbc 2.3 takes 23sec. A
>> > > little digging made me try with feasibility pump disabled, which
>> > > roughly
>> > > cut the sys time in two, but it's still nowhere close the previous
>> > > version. I'd like to know if there are parameters that can be changed
>> > > to
>> > > get closer to how fast Symphony 5.1 performs. I'm solving 0-1
>> > > problems. I
>> > > can provide MPS files if needed.
>> > >
>> > > The reason why I'm willing to switch to 5.2 is that I'm experiencing
>> > > what
>> > > seems to be a bug: when TM_gap_limit != -1, feasible solutions that
>> > > don't
>> > > respect the gap limit are produced. As far as I've been able to see,
>> > > this
>> > > bug seems to be fixed in 5.2. If you know about this bug, a quick edit
>> > > in
>> > > my 5.1 source would also do the trick.
>> > > Thanks in advance
>> > >
>> > > Pierre Le Bodic
>> > >
>> > > _______________________________________________
>> > > Symphony mailing list
>> > > Symphony at list.coin-or.org
>> > > http://list.coin-or.org/mailman/listinfo/symphony
>> > >
>> >
>> >
>> >
>> > --
>> > Dr. Ted Ralphs
>> > Associate Professor, Lehigh University
>> > (610) 628-1280
>> > ted 'at' lehigh 'dot' edu
>> > coral.ie.lehigh.edu/~ted
>> >
>> > _______________________________________________
>> > Symphony mailing list
>> > Symphony at list.coin-or.org
>> > http://list.coin-or.org/mailman/listinfo/symphony
>>
>> --
>> regards
>> Ashutosh Mahajan
>> http://coral.ie.lehigh.edu/~asm4
>>
>> _______________________________________________
>> Symphony mailing list
>> Symphony at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/symphony
>
>
> _______________________________________________
> Symphony mailing list
> Symphony at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/symphony
>
>



-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted