[Coin-discuss] BCP variable pool handling

[Matthew Galati]

Hi Jörg,

I have observed the same thing in BCP. There is a call to 
vp.remove_positives which is executed every iteration in 
BCP_lp_generate_vars. It would be easy enough to change this to only 
remove_positives every n iterations. Interestingly, there is another 
call at the end of this loop to, once again, check for positives, remove 
them and report a warning - so, perhaps there was a good reason for 
this?? You'll have to comment this out as well. Then, when the variables 
are added in BCP_lp_add_from_local_var_pool, the pool is sorted by 
reduced cost (btw, would a partial sort be more efficient here, when 
MaxVarsAdded < vp.size())? At that point, you'll want to add a check to 
make sure you only add those with negative reduced cost.

Maybe the BCP folks can comment?

Matt


> I have a question about the variable pool implemented in BCP. As far 
> as I know, variable pools are commonly used as bidirectional buffers 
> between generated columns and the LP: Newly generated variables are 
> first written to the buffer. In every iteration, a given number of 
> best variables is inserted from the variable pool into the LP. 
> Furthermore, “old” variables (which were not used in the LP for a 
> number of iterations) are taken out and written to the variable pool 
> because they could have negative reduced costs in later iterations.
>
> In BCP, there is a variable pool (BCP_lp_prob::local_var_pool) which 
> is not quite the same. Newly generated variables are first written to 
> the pool, and the number of variables inserted from the pool into the 
> LP can be controlled (parameter MaxVarsAddedPerIteration). But in 
> every iteration, all columns with positive reduced costs are deleted 
> from the variable pool. Furthermore, variables which are marked as 
> deleted in the LP are not written to the pool by default. Implementing 
> such a feature manually (by overriding 
> BCP_lp_user::select_vars_to_delete) will not have much effect as long 
> as variables with positive reduced costs are deleted in a subsequent 
> step. The local_var_pool thus currently serves as a buffer for 
> variable insertions, avoiding variables to be inserted which would 
> have positive reduced costs after insertion of a more promising subset 
> of variables.
>
> Therefore my question: Have I overseen anything? Are there features to 
> implement a pool strategy as described above? Or is there anything 
> planned in the future?
>
> Many thanks,
> Jörg
>
> _________________________________________________________________
> MSN 8 with e-mail virus protection service: 2 months FREE* 
> http://join.msn.com/?page=features/virus
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at www-124.ibm.com
> http://www-124.ibm.com/developerworks/oss/mailman/listinfo/coin-discuss


-- 
Matthew Galati
ISE Lehigh University
IBM Service Parts Solutions
610.758.4042 (Office)
610.882.0779 (Home)
magh at lehigh.edu, magal11 at us.ibm.com
http://sagan.ie.lehigh.edu/mgalati/