[SCIP] How does branching affect pricing in SCIP

[Benjamin Müller]

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/6c326784/attachment.html>