[Scip] Slow LP re-optimization after branching

[Xavier Schepler]

Good evening,


Please find 2 "hard" LP instances (don't solve them as MIP, first convert
them to LP) :

http://www.4shared.com/archive/s1NOU9gyce/ills_LPtar.html

I removed all the extra artificial variables.

deg5.lp
75 000 * 130 000
> 1 800 s. CPLEX 12.6
265 000 simplex iterations

deg7.lp
77 000 * 135 000
> 2 400 s. CPLEX 12.6
? simplex iterations (I had to stop)

Best regards,

Xavier







2014-02-26 19:46 GMT+01:00 Gerald Gamrath <gamrath at zib.de>:

> Hi Xavier,
>
> > I realized that in the LP files I sent to you,
> > there are a lot of extra artificial variables (at least one by
> > constraint),
> > whereas in the first log I sent to you, there were only two artifical
> > variables for all constraints.
> > Please excuse me for that, I had to produce results using this
> > initialization, with smaller instances, for another purpose,
> > and I forgot to change the code before generating LP files.
> > If you need them, I will be able to generate the LP files with two
> > artificial variables next week.
> yes, that would be good.
> >
> > Anyway, SCIPprintStatistics tells that, a 65000 * 20000 LP,
> > with at least 20000 artificial variables is solved in 300 sec at root
> > node.
> >
> > Then, during column generation, 6920 of 7200 seconds are spent
> > reoptimising LPs.
> > There are 35 column generation iterations.
> > All negative reduced cost columns are added at each iteration (full
> > pricing).
> >
> > In a 7200 seconds run, 223 seconds were spent pricing.
> > Almost all the time was spent solving LPs ...
> > SCIPprintStatistics output :
> >
> > Pricers            :   ExecTime  SetupTime      Calls       Vars
> >   problem variables:       0.00          -          0          0
> >   Exact pricer     :     223.51       0.01         34        605
> >
> > LP                 :       Time      Calls Iterations  Iter/call
> > Iter/sec  Time-0-It Calls-0-It
> >   primal LP        :    6920.86         34     661444   19454.24
> > 95.57       0.00          0
> >   dual LP          :      54.79          1      35700   35700.00
> > 651.58       0.00          0
> >
> > Column generation has not the time to terminate at root node.
> >
> > Is the LP solved again and again from scratch ?
>
> Yes, this looks like SCIP is solving the LP from scratch over and over
> again. This is a known issue which will be fixed in the upcoming SCIP
> release. SCIP applies an objective limit for LP solving, which means
> that the dual simplex stops when reaching the objective limit. Normally,
> the current node could be cut off, in a branch-and-price context,
> pricing has to be done, but this can also be done with the current dual
> solution values. Actually, you can see this as a kind of stabilization.
> On the other hand, the current basis is then only dual feasible and
> adding new columns leads to loosing the dual feasibility as well and the
> LP needs to be reoptimized from scratch. In particular with as many
> variables as you have, this can slow down your LP solving significantly.
>
> We are working hard on finishing the release until tomorrow, please
> check it out then and try it. It should resolve your problem and reduce
> the LP reoptimization time.
>
> Best,
> Gerald
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140227/7bf9448c/attachment.html>