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

[Gerald Gamrath]

Hi Georg,

> Yes, setting delay = true fixed the problem. Thank you so much for 
> your help!
> I thought that this setting did not apply in my case since I added all 
> variables as non-removable. Thank you for clearing up that 
> misunderstanding.
good to hear that it works now. I'm happy that I could help.

> Just to help me improve my understanding of the "initial" and 
> "removable" flags for variables (in ILP models):
>
> * If a variable is added as "initial" to the model before calling 
> SCIPsolve, its column will be included in the root LP right away. If 
> it is added as "non-initial", the root LP will not contain the 
> corresponding column, but it can be added by the variable pricer if it 
> is found to have negative reduced costs (assuming minimization).
Exactly.

> I'm a bit unsure about how this setting influences variables added 
> later on. Does it have no effect at all or does it determine whether 
> they are added to the current node's LP right away?
Yes, it determines whether it is added to the current node's LP.

> * If variables are added as "removable", their columns may be removed 
> from node LPs at any time - but after solving the node LPs, the 
> variable pricer checks whether any of these removed columns have 
> negative reduced costs and, if so, adds them back into the node LP 
> (which is then resolved if I set delay = true on my own pricer). If 
> they are added as "non-removable", their columns will always be 
> present in the node LPs of the subtree in which they were added.
Yes, this is correct. Note that non-removable columns that are added at 
another part of the tree later by the variable pricer will then also 
stay in the LP there. By the way: due to internal data structures in 
SCIP and how bases are stored, columns can only be removed from the LP 
if they were added at the same node. If they were added to the LP at an 
ancestor node, they will stay in the LP.

Best,
Gerald

>
> Is my understanding of these two parameters correct?
>
>
> Thanks again for the help :)
>
> Best,
> Georg
>
> On 18/02/2019 20.45, Gerald Gamrath wrote:
>> Hi Georg,
>>
>> this sounds like the delay flag of your pricer is set to FALSE. I 
>> would always recommend to set this to TRUE, because this ensures that 
>> your pricer is only called if none of the existing variables have 
>> negative reduced costs. Such variables will be added to the LP by the 
>> variable pricer and you normally don't want to call your own pricer 
>> for the old LP solution, but rather wait until the LP was re-optimized.
>>
>> Variables in SCIP are always globally valid, however, they are only 
>> directly added to the LP at the node where they are created (and 
>> thus, also present in the subtree rooted at that node). At other 
>> nodes, they may be added by the variable pricer, if they improve the 
>> solution.
>>
>> Please see also the FAQ for more details: 
>> https://scip.zib.de/doc-6.0.1/html/FAQ.php#faq_specificquestionsaboutcolumngenerationandbranchandpricewithscip
>>
>> Best,
>> Gerald
>>
>> On 18.02.19 12:03, Georg Brandstätter wrote:
>>> 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
>>>>
>>