[Scip] Slow LP re-optimization after branching

[Gerald Gamrath]

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