[SCIP] Unexpectedly many calls of dual LP in a Branch and Price algorithm

[Gerald Gamrath]

Dear Andreas,

sorry for the late reply. I can understand your point of view and I also 
had to think twice in order to find a possible explanation for this 
behavior. You are right that just calling a pricer which returns 
SCIP_SUCCESS and does not add any variables should not change the solver 
behavior. However, already the fact that there is an active pricer 
changes the behavior of SCIP, because some reductions, e.g., in 
propagation, can only be performed if the model description is fully 
present already. Therefore, if a pricer is present, some components of 
SCIP are disabled, which may lead to the differences you were observing.

Best,
Gerald

On 15.04.19 13:56, Linß, Andreas wrote:
>
> Dear SCIP Community,
>
> I am currently working on a Branch and Price algorithm with SCIP and 
> the C++ interface with SCIP version 6.0.1. I've noticed the hints and 
> the VRP example and implemented the callback functions. Somy pricer 
> returns *result =SCIP_SUCCESS when it has found a new variable, or it 
> could prove that no more variables with negative reduced cost exists. 
> I am solving my problem with the following settings:
>
> SCIP_CALL( SCIPsetHeuristics  (scip,SCIP_PARAMSETTING_OFF,true));
> SCIP_CALL( SCIPsetSeparating  (scip,SCIP_PARAMSETTING_OFF,true));
>  SCIP_CALL( SCIPsetLongintParam(scip,"limits/nodes", 2000));
>   SCIP_CALL( SCIPsetIntParam(scip,"pricing/maxvars",10000));
>
> I stoped the solution process for comparability after 2000 Branch and 
> Bound nodes.
>
> With a pricer, which have to generate the variables, i have 11.227 
> dual Lp calls and 2027 primal LP calls with 2902 own_pricer calls with 
> 1201 generated variables.
> With a problem with all variables an a pricer, that can not generate 
> variables, i have 9273 dual calls and 2001 own_pricer calls, with 0 
> generated variables.
> With a full problem with all variables an no pricer, i have 2837 dual 
> LP calls.
>
> The variables of case 1 and case 3 are generated the same way. The 
> only difference of these cases is the possibility to use a pricer, 
> that only returns SCIP_SUCCESS.
> So it is confusing, that the solver, with the pricer, calls dual LP 
> more often than without, although the pricer does nothing.
> I thought, that the LP is solved with the existing variables of memory 
> and model and after that, the pricing is called. The pricing can not 
> improve the model, so the LP should not be touched again. But my way 
> of thinking does not explain the difference of  2837 and 9273 calls.
>
> I am searching for an explanation, why the  dual LP is called more 
> often, when I am activating my own pricer.
> Also I hope, that you understand my point of view and I hope you have 
> an explanation for this phenomenon.
>
>
> Nice regards
> Andreas
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190526/999e3758/attachment.html>