[Scip] Lower bound in branch and price method

[Gerald Gamrath]

Hi Mahdi,

I can second Marco's guess, your pricing problem probably works incorrectly.

SCIP gets the value for the dual bound by solving the master LP to
optimality. In a branch-and-price context, this means that the
restricted master is solved to optimality, new variables are created
based on the dual values, the restricted master is solved again, etc.
When at some point, the pricer does not generate any new variable, SCIP
assumes that this means that there is no improving variable and takes
the LP value as a dual bound. If you want to stop generating variables
early in order to reduce the tailing-off effect, you need to set the
result pointer of the pricer to SCIP_DIDNOTRUN instead of SCIP_SUCCESS.
This tells SCIP that there might still be improving variables and the LP
value is no valid dual bound. See also
http://scip.zib.de/doc/html/PRICER.shtml

Do you have a minimization or maximization problem? In the latter case,
perhaps you forgot to multiply the original objective coeffcients of the
variables by -1 when creating the variable, see
http://scip.zib.de/doc/html/scip_8h.shtml#aadcc57e6efe08c07a23643d0e7fb3151

Best,
Gerald

On 06.08.2013 14:09, Marco Lübbecke wrote:
> First short: you do not generate "all" columns, that is, your pricing
> problem is buggy. Check whether you calculate reduced costs correctly,
> check whether your pricing problem formulation is correct, verify with
> toy examples that you can (and do) solve by hand for comparison.
>
> Bests,
> Marco
>
>
>
> 2013/8/6 Mahdi Noorizadegan (DIMAP) <phd09mn at mail.wbs.ac.uk
> <mailto:phd09mn at mail.wbs.ac.uk>>
>
>     Dear SCIP,
>
>     I am trying to solve a variant of VRP in SCIP within branch and
>     price algorithms.
>     The problem is that after few iterations without any dual bound
>     and infinite gap, it generates a lower bound which is higher than
>     the optimal solution of the instance I solve.
>     I was wondering if you could help me to understand how SCIP
>     generates the dual bound and why while it is still in early stages
>     it generates very high lower bound?
>
>     Thanks
>     Mahdi
>
>     _______________________________________________
>     Scip mailing list
>     Scip at zib.de <mailto:Scip at zib.de>
>     http://listserv.zib.de/mailman/listinfo/scip
>
>
>
>
> -- 
> Prof. Dr. Marco Lübbecke
> RWTH Aachen University            
> Chair of Operations Research  
> Kackertstrasse 7                          
> D-52072 Aachen                          
> Germany                                        
>
> fon / fax: +49 241 80-93362 / 92369
> marco.luebbecke at rwth-aachen.de <mailto:marco.luebbecke at rwth-aachen.de>
> www.or.rwth-aachen.de/luebbecke <http://www.or.rwth-aachen.de/luebbecke>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/pipermail/scip/attachments/20130806/8da85845/attachment.html