[SCIP] Lower bound for branch and price algorithm

[Gerald Gamrath]

This behavior changed some releases ago. In the current version, the 
pricer callbacks have return values, so that your pricer can inform SCIP 
that even though it did not add a variable, there might still be some 
improving variables and the current LP objective cannot be used as a 
dual bound.

Of course, SCIP won't be able to prove optimality, if you just do 
heuristic pricing and your pricer cannot provide any lower bounds, but 
you might want this at some nodes to speed up the process. If you can 
provide Lagrangian dual bounds (which also a heuristic pricer could do 
if it computes lower bounds for all pricing problems), you could be 
lucky to even prove optimality with a heuristic pricer. Additionally, 
even with an exact pricer, you might want to stop pricing and do early 
branching to overcome the tailing off effect.

Best,
Gerald


On 14.09.2017 11:53, Tobias Achterberg wrote:
> Note that SCIP can only provide a valid dual bound if the pricing is 
> exhaustive, i.e., if the pricer plugin will always provide at least 
> one additional column if there exists one that can potentially improve 
> the objective function.
>
> If you only have a heuristic pricer (i.e., it may return without any 
> new columns even though there may exist some that can improve the 
> objective function), then the dual bound provided by SCIP is not 
> globally valid and the whole algorithm becomes a heuristic procedure 
> instead of a complete algorithm in the sense that it will always find 
> an optimal solution.
>
> Regards,
>
> Tobias
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip