[Coin-discuss] BCP variable pool handling

[Laszlo Ladanyi]

Hi Jorg,

You are entirely right. No true variable pool exists in BCP and local_var_pool
is just a buffer that keeps those that are still promising. 

It wouldn't be very difficult to implement a basic real variable pool. It'd be
a separate process and would work very similarly to the variable generator
process (which is implemented). There are two reasons why I haven't yet
implemented the real pool: 1) laziness... I my projects I didn't need it 2) in
most column generation formulation solving the subproblem is really fast (at
least compared to resolving the LP) and it gives the column with the best
reduced cost -- so a pool doesn't really help.

If you'd like to implement a real pool I can give you suggestions, how I see
it would fit into BCP, but that we can discuss offline.

--Laci


On Fri, 9 Jan 2004, Jörg Herbers wrote:

> 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
>