[Scip] Pricing generates an already existing column

[Martin Bergner]

Hi Cristina,

somewhere in your detailed explanation, you write:
> Even
> that your comment about branching was focus on variables with upper
> bound = 0, now I am thinking that maybe the branching rule is somehow
> forbidding some of the variables. How can I check this behaviour?  I do
> not use any special rule for the branching. All the branching procedure
> is set as default.
This is probably the issue:
When you don't specify a branching rule, SCIP branches on the priced
variables. If they are binary, they are fixed to one in one branch and
zero in the other. If the variable is fixed to zero, then nothing in the
pricing problem forbids it from being generated again.

Suppose now you have a non-degenerate variable in the basis that is
removed by fixing it to zero. Since nothing in the pricing forbids it
from doing so, it regenerates that variable that has been fixed. After
all, this variable is highly attractive (negative reduced cost) and
should be put into the basis, it was there before it was forcibly
removed by branching.

Do you see the problem? Whenever SCIP fixes a variable to zero, your
pricing problem generates it again (and you thus have the problem you see).

The remedy is: You have to (and in fact everyone  when using
branch-and-price with SCIP with integral priced variables should)
implement your own branching rule (maybe Ryan-Foster or something more
general, depending on your problem at hand).

I hope I could clarify the issue.

Regards,
Martin


-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4514 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140528/9e246466/attachment.p7s>