[SCIP] Negative Reduced Cost Vars not in LP

[André Mazal Krauss]

 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é
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20220926/34c81c45/attachment.html>