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

[Horváth Markó]

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