[Scip] Slow LP re-optimization after branching

Xavier Schepler xavier.schepler at gmail.com
Fri Feb 28 13:53:36 CET 2014


Dear Michael,

I hope the following link will work :

https://drive.google.com/file/d/0B9ZBUxydypK8anlZOUxMNEFYX3c/edit?usp=sharing

The last time, the web server converted my tar.gz file to a tar file.

Best,

Xavier


2014-02-28 3:58 GMT+01:00 <michael.winkler at zib.de>:

> Hi Xavier,
>
> can you please use some site, where no social network account is necessary
> to download the files. (By the way, if I'm not mistaken last time you
> uploaded a file with the extension tar.gz, but it was only a tar file.)
>
> But, from your results, it looks like really hard LPs...
>
> Best, Michael
>
>
> > 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
> >>
> >>
> > _______________________________________________
> > Scip mailing list
> > Scip at zib.de
> > http://listserv.zib.de/mailman/listinfo/scip
> >
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140228/d8d9742c/attachment.html>


More information about the Scip mailing list