[Scip] Regenerating column that is at it's upper bound

Sebastian Ruther Sebastian.Ruther at uon.edu.au
Tue Aug 23 09:24:36 MEST 2011


  Hello,

my branch and price algorithm regenerates a column. I don't think I have 
a bug or at least it is not an obvious one because I manually checked 
that the dual values are handled correctly in the pricing problem and 
that the column gets added to the master problem correctly. When I add a 
column I generate a binary variable and call SCIPchgVarUbLazy(scip, var, 
1.0).

The original variable is generated in iteration 10, the new one in 119. 
When it regenerates, the original column is at value 1 in the lp 
solution. So the tasks the new column wants to do are covered (set 
partitioning constraints in the master problem).

When I'm debugging this I calculate the dual objective function by 
simply summing the dual values of the constraints (set partitioning and 
set packing constriants) or multiplying them by SCIPgetRhsLinear if the 
constraint is linear. I compare that to SCIPgetLPObjval(scip). With this 
I want to check if the master problem LP was solved to optimality. The 
two values are the same for all iterations up to iteration number 118, 
in which
PrimalLP = 21315.000000000000
DualLP =  21369.999999999985
then in iteration 119, when the column gets regenerated, I have
PrimalLP = 21528.094557189928
DualLP = 21600.875760878880
Note also that this is a different node than iteration 118.
However none of the branching decisions affect this pricing problem (I 
have multiple pricing problems). In fact nothing is fixed in this 
pricing problem.

Why are the PrimalLP and DualLP values not the same?
Any ideas why I regenerate the column? How do lazy bounds work in scip?

Regards,
Sebastian



More information about the Scip mailing list