[SCIP] How does branching affect pricing in SCIP

[Benjamin Müller]

Dear Myroslav,

maybe I need to clarify my previous answer: In the z_P = 0 branch, you 
want to find a path with the most negative reduced cost that is not P 
and has most negative reduced costs. After solving the corresponding 
pricing problem, you either add a new variable z_P' or you proved that 
the continuous relaxation in the current (local) node has been solved to 
optimality. In both cases, you don't add a variable that has been 
generated already.

To summarize it, you need to respect the branching decisions in order to 
ensure that you generate all variables that are needed for solving the 
LP relaxation of a local node to optimality. Branching on the master 
variables usually changes the pricing problems drastically (e.g., 
shortest path -> k-shortest path).

Best,
Benny


On 08/30/2018 12:15 PM, myroslav wrote:
>
> 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/23718a56/attachment.html>