[Coin-discuss] BCP compute_lower_bound

[Matthew Galati]

I have a question pertaining to the logical flow in BCP. If a user wants 
to write a branch and price application, it seems, there should be a 
valid default implementation of compute_lower_bound. When doing column 
generation you can determine a valid lower bound by checking if there 
are any new columns with negative reduced cost. If one exists, then we 
cannot use the current LP solution as a valid lower bound and we should 
just return the old_lower_bound (unless we want to do something smart, 
e.g. Farley, Vanderbeck, etc. - but this can be left to the user to 
implement). If no columns exist with negative reduced cost, then the LP 
solution does give a valid lower bound.

In BCP, as far as I can tell, it seems that compute_lower_bound is 
called *before* the call to generation of variables 
(generate_vars_in_lp). The default checks the col_gen status to see if 
columns are going to be generated. Given the order, the status will 
always be that columns will be generated. Hence, the default simply 
returns old_lower_bound. However, the initial lower bound is -inf. 
Therefore, it seems, the lower bound used to prune is always -inf??

This, of course, can be gotten around by forcing the user to derive 
compute_lower_bound. In this function, the user would need to look for 
new variables with negative reduced cost. However, this is exactly the 
work that needs to be done in generate_vars_in_lp (which the user must 
derive). So, it seems to me, that BCP should be calling 
generate_vars_in_lp before compute_lower_bound. This would allow for a 
good default implementation of compute_lower_bound, as well as putting 
the work of doing variable generation back into its proper function: 
generate_vars_in_lp.

It is possible that there is some interaction when doing full branch 
price AND cut that makes this impossible. Am I missing something?

Thanks,
Matt

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