[SCIP] duplicate variables found during pricing / existing variables with negative reduced cost

[Gerald Gamrath]

Dear Georg,

the LP is solved after each pricing round (if variables were added) and 
the reduced costs should be reliable at the start of scip_redcost. The 
first thing coming to my mind: do you have an upper bound on that 
variable? In that case, if it is nonbasic on its upper bound, the 
variable needs to have non-positive instead of non-negative reduced cost 
for the LP to be solved optimally.

Otherwise, we need to have a deeper look. I agree that the reduced costs 
are quite negative and this does not look like a numerical issue. Can 
you try running with SoPlex to see if the issue comes up there as well? 
Just to make sure that it is not an issue in our interface to CPLEX.

Best,
Gerald

On 14.02.19 18:59, Georg Brandstätter wrote:
> Dear SCIP developers,
>
> I'm currently facing a rather strange problem with my branch-and-price 
> algorithm.
>
> When solving my pricing problem, I find columns with negative reduced 
> costs that already exist in the current LP. When querying the reduced 
> costs of the already existing column with SCIPgetVarRedcost at the 
> start of the scip_redcost method, the existing variables also have the 
> exact same negative reduced costs as the ones I just found during 
> pricing and want to add. These reduced costs are well negative (e.g., 
> -6.5), so I would assume that it is not simply a numerical issue with 
> my LP solver.
>
> SCIPgetLPSolstat returns 1, which would indicate that the LP was 
> optimally solved. If that is the case, how can it be that any of the 
> existing variables have negative reduced costs?
> My original ILP model is a maximization problem, but SCIP transforms 
> it into a minimization problem as usual. This would suggest to me that 
> all variables should have non-negative reduced costs in an optimal LP 
> solution. The reduced costs of all other variables is nonnegative (or 
> very slightly negative, e.g., -1e-15, which I'm assuming is due to 
> some numerical issues).
>
> If I simply add the duplicate columns to the model (or skip adding 
> them) and continue with the branch-and-price, it eventually finds an 
> optimal solution to the problem (the same solution as a different, 
> compact ILP - so I'm assuming it is correct).
>
> Can you help me understand what is going on here? Are the values that 
> I get from SCIPgetVarRedcost unreliable when I query them at the start 
> of scip_redcost? I'm seeing LP solver output between the different 
> calls to scip_redcost, so it looks like it is actually solving the LP 
> between pricing rounds.
>
> I'm using SCIP 6.0.1 with CPLEX 12.8 as an LP solver.
>
> All the best,
> Georg
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip