[Scip] Pricing generates an already existing column

[Gerald Gamrath]

Hi Christina,

all branching rules in SCIP do branching on variables, i.e., split the
domain of a single variable when branching. This is the standard way to
do it for branch-and-cut, but for branch-and-price, this does not work
well, because the pricing would need to know that a variable was for
example fixed to 0 and must not be regenerated. This can often not be
accomplished without destroying the structure of the pricing problem
needed for the fast algorithms to solve them.

In branch-and-price, you typically implement your own branching rule
which does not branch on variables, but on constraints or decisions in
the pricing problem. For example, the Ryan and Foster branching rule
applied to binpacking decides whether two items will be packed into the
same bin or two different bins. This leads to a modification of the
pricing problem as well as forbidding some of the master variables which
do not comply with the current branching decisions. Alternatively, you
could branch on variables of the underlying structure represented by the
compact formulation. This means, if your variables correspond to paths
in a graph, you could branch on the decision whether an arc is used or not.

Please check out the binpacking and coloring example for examples of
Ryan and Foster branching rules.

Best,
Gerald

On 03.06.2014 10:45, Cristina Núñez del Toro wrote:
> Hello Martin,
>
> I think I understand the problem. I just have a couple of questions:
>
>  1. I can not see clearly how this situation can be fixed by
>     implementing my own branching rule
>  2. I have checked that there some branching rules that are currently
>     available on SCIP.  How can I know which branching rule
>     does SCIP uses by default? Because these branching rules seem to
>     be quite general, I would like to try first on swapping among
>     them. Is there a way to make a callback to force the use of one of
>     them instead of the default one? If not, is the only way to
>     implement my personalized branching rule by adding explicitly a
>     constraint handler?
>
> Thanks in advance.
>
>
>
> ---
> Cristina Nuñez
>
>
> 2014-05-28 20:46 GMT+02:00 Martin Bergner <bergner at or.rwth-aachen.de
> <mailto:bergner at or.rwth-aachen.de>>:
>
>     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
>
>
>
>
>
> -- 
> ---
> Cristina Nuñez

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140603/c80f1971/attachment.html>