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

[Georg Brandstätter]

Hi, Gerald

I've also tried using SoPlex as an LP solver to no avail - the problem 
persists, but happens at a different node in the B&B tree.
My variables do not have an upper bound (it is set so 
SCIPinfinity(scip)) and a lower bound of 0. And in case that should be 
relevant, they all have negative objective coefficients.

I also think that I have now found an explanation for this strange 
behavior. The LP I get when calling SCIPwriteLP at the start of 
scip_redcost seems to be incomplete.

Specifically, it is missing some of the previously priced columns (in a 
specific example, I've already priced 414 variables in previous 
iterations, but the LP file only contains the first 288). Specifically, 
all those columns that have negative reduced cost are missing, which 
would of course explain why I find them again when pricing.
Curiously, the model is also missing some constraints that I definitely 
added to the model (i.e, they are present in the LP file I get when 
calling SCIPwriteOrigProblem).


I've already tried to rule out some possible reasons that I could think of:

* preprocessing: I've deactivated both regular and LP preprocessing 
("lp/presolving" = false, "presolving/maxrounds" = 0), but the problem 
persists. It simply happens at different nodes in the B&B tree.

* threading problems: I've set both "lp/threads" = 1 and 
"parallel/maxnthreads" = 1, but nothing changes. Also, I'm calling 
SCIPsolve, which as I understand it is always single-threaded.

* variables are only added to the local LP, not the global one: I'm 
adding new columns with

SCIPcreateVar(scip, &newVar, name.c_str(), 0, SCIPinfinity(scip), 
objCoef, SCIP_VARTYPE_CONTINUOUS, false, false, nullptr, nullptr, 
nullptr, nullptr, nullptr);
SCIPaddPricedVar(scip, newVar, -objCoef);

which I'm thinking should add them globally. I've also tried setting 
initial = true and removable = true to no avail.
Also, the priced columns that are present in the LP are created in 
different parts of the B&B tree, not only in the ancestors of the node 
where this happens.

In case that helps: in my master problem, I'm using both binary 
branching on some integer variables (which are added to the problem 
statically, i.e., not priced) and a custom Ryan-Foster-style branching 
scheme on the priced variables. No Ryan-Foster branchings were made 
until the error occurs.


I'm sure I'm missing something really obvious here, but I'm having a 
hard time figuring out what that might be. I hope you'll be able to help 
me :)

Best,
Georg


On 18/02/2019 08.58, Gerald Gamrath wrote:
> 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
>