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

[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