[SCIP] Lower bound for branch and price algorithm

[Gerald Gamrath]

Dear Amir,

in a branch-and-price algorithm, you solve every node LP via column 
generation. At the end of that process, the current LP solution provides 
a valid lower bound. This is what SCIP installs as lower bound of the 
node, and if you call SCIPgetDualBound after the root LP finished 
solving with column generation (and before the branch-and-bound 
continued), you will get this bound.

Of course, there are other means to compute valid lower bound, e.g., the 
Lagrangian dual bound if you solved all pricing problems to optimality 
in one pricing round and know an upper bound on the sum of solution 
values for all variables of a pricing problem in each LP solution. This 
cannot be done automatically, because you implement the pricer yourself, 
however, if you can compute such a bound, you can pass it to SCIP via 
the lowerbound pointer given to the pricing callback.

Best,
Gerald


On 13.09.2017 21:24, Amir Mansouri wrote:
>
> Hi SCIPers,
>
> I am solving an integer problem using a branch and price algorithm.
>
> I need to have a global lower bound for my problem.
>
> Note that all columns are not included in the root node. So the linear 
> programming relaxation does not work here.
>
> Does scipgetdualbound in the root node provide a lower bound for my 
> problem?
>
> If it does, could you provide me with detail of computing the lower bound?
>
> Which theorem or inequality is used to get the lower bound?
>
> If it does not, how can I get a lower bound?
>
> Thanks,
>
> Amir
>
>
>
> _______________________________________________
> 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/20170914/37e08feb/attachment.html>