[Scip] much time when solving LP in B&price.

[Matthias Miltenberger]

Hi Cristina,

if you add new variables your new LP relaxation will be primal feasible. 
If you branch, the LP relaxation of the new node will be dual feasible. 
You set the new bounds on the branching variable to make it primal 
infeasible - not much else is changed, though.  SCIP always tries to 
call the appropriate simplex variant based on the current feasibility 
status.

You should have a look at the statistics and the log to see how many LP 
iterations are performed in the root and for re-optimizations in the tree.

You could definitely try changing the pricing method of the LP solver to 
see whether that improves the performance on your instances. Partial 
pricing of SoPlex usually leads to an increase of iterations since you 
don't consider all candidates.

SCIPaddPricedVar() looks at the pricing score to decide which variable 
enters the LP. This is only done when you add more than 
pricing/maxvars[root] variables in one pricing round.

all the best
Matthias

On 21.04.2015 16:07, Cristina Núñez del Toro wrote:
> Hello all,
>
> I'm have implemented a Branch&Price algorithm but I have some 
> questions about the LP optimization behavior. When I try a quite big 
> instance, my implementation spends a lot of time obtaining the LP 
> solution (not only for the pricing routine, after adding variables but 
> also when the first time in the node). So, before thinking about 
> deleting variables and/or changing parameters for remove columns, I 
> would like to have clear first some issues about the LP 
> re-optimization. For example:
>
> 1) How does LP is solved after adding new (pricing) variables? it is 
> used primal simplex, dual simplex or it is optimized from scratch?
>
> 2) How does the LP is solved when it first enters to a node after 
> branching? it is used primal simplex, dual simplex or it is optimized 
> from scratch?
>
> About 1), my desire would be to re-optimize using primal simplex, so 
> the new variables could be the very first candidates to enter to the 
> basis. In particular, I would like to try 'partial' LP pricing 
> strategy as an option in reducing the cpu time. Changing this 
> parameter is applied only if I use SoPlex as LP solver or it is 
> applied to any other LP solver (Cplex for example) as well?
>
> Another thing that could be related (or not) with this is:
>
> 3) How does the variable's pricing score in "SCIPaddPricedVar( SCIP * 
> scip, SCIP_VAR* var, SCIP_Real score)" is related with the LP 
> reoptimization. I really appreciate if you could give me more 
> information about this.
>
> 	
> 	
> 	
>
> 	
> 	
> 	
>
> 	
> 	
> 	
>
> 	
> 	
>
> Best regards,
>
>
> -- 
> ---
> Cristina Nuñez
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-- 
\__________________

Matthias Miltenberger
Zuse Institute Berlin
Takustr. 7, 14195 Berlin
www.zib.de/miltenberger
miltenberger at zib.de
+49 (30) 841 85-245

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150424/b02bcdea/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5149 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150424/b02bcdea/attachment.p7s>