[Scip] Slow LP re-optimization after branching

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