[SCIP] How to deactivate aging and avoid scip internal pricer ?

[Sandra Ulrich Ngueveu]

Hello Gerald,

First of all, thank you for taking the time for the detailed answer.

For the moment we let scip handle all branching decisions and do not 
generate valid inequalities, therefore we have not yet implemented the 
constraint handler.

We modified our pricer so as not to forbid the generation of columns 
that may have already been generated during previous iterations. That 
did not solve our issue, which means that it had nothing to do with 
scip's internal pricer (otherwise we would have simply regenerated the 
right columns and converged to the right solution).

We are still investigating our issue and the vbc visualisation tool 
helped identifying that some nodes where declared infeasible when we did 
not think that they were. This remains to be confirmed, but the issue 
may be in the model itself.

Again, thank you very much for the support,

Best regards,

Sandra



Le 03/07/2018 à 14:05, Gerald Gamrath a écrit :
> Dear Sandra,
>
> I thought about this again and I am quite sure where this large number 
> originates from. As you might know, all variables that you create 
> during pricing are valid globally. However, the corresponding columns 
> are only added to the current LP. When jumping through the tree, the 
> LP is restored to the state it had when this node (or the parent node) 
> was processed, so that a warmstart can be performed from the basis of 
> the parent node. The variables that you priced in at other parts of 
> the tree, but whose columns are then not part of the LP anymore, are 
> then potentially added to the LP by the variable pricer of SCIP. The 
> more you proceed in the tree search, the more open nodes you have at 
> which columns found at other nodes may be added to the LP, so this 
> number increases faster.
>
> There is no option to disable this. You might want to consider setting 
> the delay flag of your pricer to FALSE, if you did not do so already, 
> so that you pricer is only called if the variable pricer did not add a 
> column in this pricing round.
>
> Concerning your issue: I agree that the optimal solution should be the 
> same as long as you always add at least one improving column if there 
> exists one. But adding more or less columns changes the LP and might 
> lead to different LP solutions, thus a changed branch-and-bound tree, 
> and different solutions being found. In rare cases, this might trigger 
> a bug in SCIP that you do not come across otherwise, or perhaps also 
> your pricer stops because reduced costs changed slightly and are now 
> zero or not zero anymore (within tolerances).
>
> What you could do (but I would only recommend this for debugging): I 
> assume you have a constraint handler that takes care of your branching 
> decisions and fixes variables locally to 0 that were created at other 
> nodes and to not comply with the branching decision. A very drastic 
> step would be to just fix all variables to 0 that have been created at 
> other nodes. This would as a consequence disable the variable pricer 
> and only your pricer could add variables.
>
> Best,
> Gerald
>
> On 28.06.2018 09:01, Sandra Ulrich Ngueveu wrote:
>>
>> Hello Gerald,
>>
>> Thank you very much for your reply.
>>
>> The model is small (302 variables).
>>
>> Setting parameter age limit to -1 does not seem to deactivate scip 
>> internal pricing (442 variables from our pricing versus 66334 from 
>> scip).
>>
>> Also, let me specify that at the beginning of each pricing 
>> phase///PRICERREDCOST, /we displayed the number of variables 
>> previously added by our pricer and the result of 
>> SCIPgetNPricevarsFound. During several iterations, the two numbers 
>> were the same. But at some point the second number becomes higher 
>> than the first, and the difference between the two numbers increases 
>> until the end of the branch-and-price.
>>
>> The statistics displayed at the end (with scipprintstatistics) showed 
>> that scip's pricer is very fast (0.03s), so we not longer expect to 
>> gain any speed-up there.
>>
>> But we would still like to deactivate it if possible, to help us 
>> investigating the following issue : Let's consider two disjoint sets 
>> of columns S1 and S2, and their union Sall (= S1 U S2). We are trying 
>> to understand why in our branch-and-price, adding Sall leads to a 
>> worse final solution than adding S1 example. Therefore we are 
>> carefully rechecking our code and we would like to deactivate scip's 
>> pricer if possible.
>>
>> Best regards,
>>
>> Sandra
>>
>>
>> Le 25/06/2018 à 19:19, Gerald Gamrath a écrit :
>>> Dear Sandra,
>>>
>>> I don't think that SCIPgetNPricevarsFound returns what you are 
>>> interested in. As far as I can see, this is the total number of 
>>> variables that were added to the to the pricestore. This may be 
>>> variables "priced" by SCIP, but also the variables you priced, as 
>>> well as all variables in your original formulation, that go through 
>>> the pricestore once to enter the LP. Perhaps your original 
>>> formulation is quite large?
>>>
>>> Setting the age limit to -1 should normally do the trick. There are 
>>> other things like "lp/cleanupcols(root)", but those are disabled by 
>>> default.
>>>
>>> When you look at the statistics after solving ("disp stat" in the 
>>> interactive shell or SCIPprintStatistics()), you should see how many 
>>> variables are really added by your pricer and by the internal SCIP 
>>> pricing ("problem variables").  Is there a nonzero number for the 
>>> latter?
>>>
>>> Best,
>>> Gerald
>>>
>>> On 25.06.2018 18:28, Sandra Ulrich Ngueveu wrote:
>>>> Hello,
>>>>
>>>> We are doing a Branch-and-Price with SCIP. Using function 
>>>> "SCIPgetNPricevarsFound", we realized that a very higher number of 
>>>> variables were "priced" by scip, compared to the number of columns 
>>>> that we explicitely added (127253 instead of 475).
>>>>
>>>> We would like to deactivate such internal pricing (which according 
>>>> to some forum is related to column aging) just to verify if the 
>>>> code would be faster for our specific problem. We tried setting 
>>>> parameter lp/colagelimit to -1, but the number of additional 
>>>> pricedvars declared by scip remained unchanged.
>>>>
>>>> Could you please tell us if there is another parameter we could 
>>>> activate or deactivate to achieve the desired behaviour ?
>>>>
>>>> Best regards,
>>>>
>>>> Sandra U. Ngueveu
>>>>
>>>
>>
>> -- 
>>
>> Maître de Conférences / Associate Professor
>> -----------------------------------------------
>> http://homepages.laas.fr/sungueve
>> -----------------------------------------------
>> ngueveu at laas.fr
>> Equipe ROC
>> LAAS-CNRS
>> 7 avenue du Colonel Roche
>> 31031 Toulouse Cedex 4 - France
>> -----------------------------------------------
>> sandra.ngueveu at enseeiht.fr
>> Département GEA
>> INP-ENSEEIHT
>> 2 rue Charles Camichel
>> 31071 Toulouse - France
>

-- 

Maître de Conférences / Associate Professor
-----------------------------------------------
http://homepages.laas.fr/sungueve
-----------------------------------------------
ngueveu at laas.fr
Equipe ROC
LAAS-CNRS
7 avenue du Colonel Roche
31031 Toulouse Cedex 4 - France
-----------------------------------------------
sandra.ngueveu at enseeiht.fr
Département GEA
INP-ENSEEIHT
2 rue Charles Camichel
31071 Toulouse - France

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