[SCIP] LP objective value is lower than the node lower bound

[Gerald Gamrath]

Hi Marko,

sorry for the late reply.

Variables in SCIP are always globally valid. When a node is focused, the 
set of columns is always equal to the final active columns of the father 
node (note that 'removable' columns may be removed from the LP directly 
before a node's processing is done). However, those variables may be 
priced to the LP automatically by the 'problem variables' pricer, which 
is normally called before your pricer (and your pricer is skipped in the 
current pricing round, if its DELAY flag is set to TRUE, which is 
default and normally what you want).

Therefore, concerning our point 2) I guess that SCIP adds the columns of 
some of the variables created in node 2 to your LP in node 3, since they 
have negative reduced costs. If they are not valid at that node, you 
need to locally fix them to zero, see 
http://scip.zib.de/doc/html/FAQ.php#pricerandnodedata

Concerning point 1), I am not sure. First, checking the number of 
columns in the LPi may not be what you want, since this is not updated 
during pricing, but only when an LP is solved and the LP data is flushed 
to the LPi. Second, how many variables do you price? There is a limit of 
100 for the number of columns added to the LP per round. If you add 
more, you should change the parameter 'pricing/maxvars'. Third, did you 
set the 'initial' flag of your variables to TRUE? Otherwise, they are 
not automatically added to the LP, but only dynamically via the 'problem 
variables' pricer.

I hope that helps.

Best,
Gerald


Am 17.03.2016 um 12:58 schrieb Horváth Markó:
> Hi all,
>
> I have made some further investigation, and I have some questions.
>
> 1) When I add a (priced or initial) variable to the problem I set flag 
> 'removable' to FALSE. Thus, at the root (as I expected) the number of 
> variables (via SCIPgetNVars) is equal to the number of columns (via 
> SCIPlpiGetNCols), however, at the second B&B-node the number of 
> variables (during the pricing procedure) is greater then the number of 
> columns. Why does SCIP discard some of my variables in spite of my 
> settings?
>
> 2) At a B&B-node, when SCIP focuses on that node the number of columns 
> (via SCIPlpiGetNCols) is equal to the final number of columns of the 
> parent B&B-node, as I expected. However, (e.g., at node 3) before my 
> pricer is called, SCIP adds some extra columns to the problem which 
> cause the malfunction I described in the previous mail. Why does SCIP 
> adds these variables (columns) to the problem? And how can I prevent 
> this?
>
> Regards,
> Marko
>
> 2016.03.09. 10:17 keltezéssel, Horváth Markó írta:
>> Dear all,
>>
>> I'm again dealing with a branch-and-price procedure using SCIP-3.2.0 
>> (also SCIP-3.1.1 and SCIP-3.2.1) with SoPlex on Windows 7.
>> I'm using binary variables and some implicit integer variables in a 
>> minimization problem.
>> For the binary variables I use lazy upper bounds (since constraints 
>> ensure that their values will not exceed 1).
>> I've written my own pricer and my own branching rule.
>> The pricer generates new binary variables (with lazy upper bound) and 
>> the branching rule changes upper bounds via SCIPchgVarUbNode.
>>
>> When I apply breadthfirst node selection I get the following result:
>> 1) after the root node solved:
>>    - SCIPgetLPObjval = 32904.700
>>    - SCIPgetPrimalbound = 33088.400
>>    - my branching rule creates 4 children: nodes 2,3,4 and 5
>> 2) at the first depth (nodes 2,3,4 and 5) everything is okay:
>>   2.1) after node 2 was completely solved with cut & price:
>>        - SCIPnodeGetLowerbound = 32904.700
>>        - SCIPgetDualbound = 32904.700
>>        - SCIPgetLPObjval = 32931.035
>>        - SCIPgetPrimalbound = 33088.400
>>        - my branching rule creates 4 children: nodes 6,7,8 and 9
>>   2.2) after node 3 was completely solved with cut & price:
>>        - SCIPnodeGetLowerbound = 32904.700
>>        - SCIPgetDualbound = 32904.700
>>        - SCIPgetLPObjval = 32909.886
>>        - SCIPgetPrimalbound = 33088.400
>>   2.3) after node 4 was completely solved with cut & price:
>>        - SCIPnodeGetLowerbound = 32904.700
>>        - SCIPgetDualbound = 32904.700
>>        - SCIPgetLPObjval = 32907.817
>>        - SCIPgetPrimalbound = 33088.400
>>   2.4) after node 5 was completely solved with cut & price:
>>        - SCIPnodeGetLowerbound = 32904.700
>>        - SCIPgetDualbound = 32904.700
>>        - SCIPgetLPObjval = 32934.992
>>        - SCIPgetPrimalbound = 33088.400
>> 3) at node 6 something went wrong as I get:
>>    3.1) after node 6 was completely solved with cut & price:
>>        - SCIPnodeGetLowerbound = 32931.035
>>        - SCIPgetDualbound = 32907.817
>>        - SCIPgetLPObjval = 32930.200
>>        - SCIPgetPrimalbound = 33088.400
>>
>>    SCIPnodeGetLowerbound and SCIPgetDualbound are what I expected, 
>> however SCIPgetLPObjval is incorrect, since it is lower (32930.200) 
>> than the node lower bound (32931.035).
>>    At first sight, I thought my pricer is wrong (it may add invalid 
>> columns to the problem), but I checked the initial LP of node 7:
>>
>>    3.2) after the initial LP of node 7 was solved:
>>        - SCIPnodeGetLowerbound = 32931.035
>>        - SCIPgetDualbound = 32907.817
>>        - SCIPgetLPObjval = 32929.542
>>        - SCIPgetPrimalbound = 33088.400
>>
>>    That is, the initial LP has lower optimal value (32929.542) than 
>> the node lower bound (32931.035).
>>    So, my pricer can not cause the problem since in this case it does 
>> not add any new column to the problem.
>>    To checked this, I wrote the last LP of node 2 (catching event 
>> SCIP_EVENTTYPE_LPSOLVED) and the first LP of node 7 (catching event 
>> SCIP_EVENTTYPE_FIRSTLPSOLVED).
>>    As I expected, the only difference between these files is that 
>> some variables have upper bound 0 in the second file and no upper 
>> bound in the first one.
>>    When I solve these LPs with a standalone solver I get that the 
>> optimum value of the first LP of node 7 is 32933.850, however (as I 
>> explained above) in my branch-and-price procedure SCIPgetLPObjval 
>> gives 32929.542.
>>
>> Another curiosity, that when I use dfs node selection (i.e, node 6 is 
>> selected after node 2 is solved) this problem does not occur, that is 
>> SCIPgetLPObjval >= SCIPnodeGetLowerbound always holds.
>>
>> I would be grateful, if you could help me to find the source of this 
>> malfunction (if it is).
>>
>> Best Regards,
>> Marko
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip