[SCIP] How does branching affect pricing in SCIP

[myroslav]

Dear Benny,


thanks a lot for the example! I see that the pricing problem is changed 
when we add a branching constraint  for a variable that is already in 
the model but the point that I miss is why we would want to generate the 
same variable again. If z_P has already been generated, then SCIP knows 
about it. So we can simply algorithmically  prevent generating it again, 
by putting an if-statement in the pricing algorithm. Why would we even 
want to compute its reduced cost, since the variable is already generated?

I can only think of one scenario when an already generated variable is 
added again:  the variable z_P has been generated at some node of the 
branching tree, since SCIP always adds variables globally, it also adds 
this variable to all the other nodes(even those which are not in the 
sub-tree of the node where z_P was generated) by using the SCIP default 
variable pricer which uses its own pricing algorithm(that's what the 
SCIP default variable pricer does, right?). If this scenario is wrong, 
please let me know, because then I don't quite understand how SCIP works.


Sincerely,

Myroslav



On 30/08/2018 11:10, Benjamin Müller wrote:
> Dear Myroslav,
>
> branching on a generated variable introduces a constraint whose dual 
> multiplier needs to be considered in the objective function of the 
> following pricing problems (when the added constraint is active). This 
> might change the nature of the pricing problems completely. Imagine a 
> branch-and-price example where the pricing problem is a classical 
> shortest path problem. Let z_P the variable corresponding to a path P 
> that has been generated. In the branch z_P = 0 you need to ensure that 
> your pricing problem doesn't generate P again. This changes your 
> pricing problem to a k-shortest path problem.
>
> I left out most of the details, but there is plenty of literature 
> about branching rules in branch-and-price. An example of how a 
> branching rule interacts nicely with the pricing problem is shown in 
> the Binpacking example of SCIP, see here 
> <http://scip.zib.de/doc-6.0.0/html/BINPACKING_MAIN.php> for more details.
>
> Best,
> Benny
>
> On 08/29/2018 12:17 PM, myroslav wrote:
>> Dear SCIP community,
>>
>>
>> I wanted to ask about how branching affects pricing and how it is 
>> managed in SCIP.  If I understand how variables are added in SCIP,  I 
>> can't think of a scenario when branching decisions really affect 
>> pricing.  A branching decision is made on variables known to SCIP 
>> (those that have been already generated/ present in SCIP), so a 
>> branching constraint involving these variables is not taken into 
>> account when we price new variables. I would appreciate if someone 
>> could clear that out.
>>
>>
>> Thanks,
>>
>> Myroslav
>>
>> _______________________________________________
>> 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/20180830/5aabfdc7/attachment.html>