[SCIP] Negative Reduced Cost Vars not in LP

[Gerald Gamrath]

Hi André,

SCIPvarIsInLp returns whether the variable is in the LP at the current 
node. As you mentioned, a variable may not be in the LP because it is 
removable and was aged out. Another reason why a variable may not be in 
the LP is if it was priced at another node of the branch-and-bound tree. 
Then, it was added to the LP there, but when SCIP jumps to another node 
in the tree, only the variables that were in the LP at its parent node 
will be in the LP initially.

Did you set PRICER_DELAY to TRUE for your pricer? The problem variable 
pricer adds existing variables with negative reduced costs to the LP and 
will be called before your pricer. If PRICER_DELAY is TRUE, your pricer 
won't be called in a pricing round where already variables have been 
added, i.e., if the variable pricer found existing variables with 
negative reduced costs, those will be added, the LP will be reoptimized, 
and a new pricing round will be started. Thus, when your pricer is 
called, there should not be any columns with negative reduced costs.

Best,

Gerald

On 9/26/22 08:00, André Mazal Krauss wrote:
> Hello SCIP team,
>
> I'm currently working on a VRP-related application, using SCIP.  I'm 
> using a Set Partitioning formulation with Branch & Price, and my 
> formulation is a minimization problem. In fact, I've already asked a 
> question about a month ago, and this is related to the same application.
>
> At that time, I was having serious problems with duplicate routes. 
> After following your suggestions and working more by myself on the 
> problem, I've managed to /almost/ eliminate the pricing of repeated 
> routes. In fact, while previously it was a certain occurrence, now I'm 
> finding about 100 repeated routes across my 1500 test instances. 
> Anyway, I wanted to understand what was going on and try to eliminate 
> them entirely.
>
> Upon investigating this, I've noticed a common trait between all these 
> repeated routes being found. 1. The problem persists even when I relax 
> the formulation and use continuous variables; 2. The negative RC my 
> pricing has computed matches exactly with the one given by 
> SCIPgetVarRedCost; 3. the already existing variable is /always/ active 
> ( ie. SCIPvarIsActive is true), but is /never/ in the LP (ie. 
> SCIPvarIsInLp is false); 4. upon inspecting the other variables in the 
> problem, I've noticed that there are typically several active 
> variables with negative RCs, but not in the LP; it's just that 
> sometimes I happened to price one of them again.
>
> I found this quite strange. How does this make sense? If the variables 
> have negative RCs, shouldn't SCIP put them in the LP and use them? I'm 
> not sure I understand exactly what SCIPvarIsInLp means. How does it 
> relate to the variable being removable and/or deletable? I've tried 
> changing my variable creation to make them /not /removable and /not/ 
> deletable, but this had no impact whatsoever. If I price a variable 
> and it isn't in the LP anymore, should it be added again? When and why 
> would SCIP decide to remove a variable RC from the LP?
>
> I was thinking for some time that this could maybe be explained by my 
> primal problem having multiple optimal solutions, which could, in 
> turn, mean the dual has multiple optimal solutions, and my pricing 
> algorithm would be somehow affected by this. But then again, I may be 
> overthinking this and the problem may be simpler, or maybe not a 
> problem at all. It really depends on what SCIPvarIsInLp actually means.
>
> Note: I have read the FAQ entry "Why are not all variables in the 
> LP?", but it does not seem to address my case since I have tested 
> without branching and the problem persists even when I set removable 
> to false in all variables.
>
> Thanks again for your help,
> André
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20220926/f8a4205c/attachment.html>