[Coin-discuss] BCP compute_lower_bound

[Laszlo Ladanyi]

Matt,

Actually, the compute_lower_bound method should be pure virtual method, the
user should always override it. Except that then plain branch&cut codes
wouldn't compile...

Anyway, why do I want it to be overridden (or more precisely, why I don't
think that BCP should update the true lower bound (tlb) to the LP value)?
Well, in many cases the user will not want to spend lots of time generating
cols, except when he must, i.e., if the 4th argument (from_fathom) of
generate_vars_in_lp is true. But then BCP can't update the tlb to the value of
the LP even if no columns were generated. It's quite conceivable that the user
just does quick colgen, if no cols are generated then branching happens and
eventually a node would be fathomed, and then the user spends lots of time
generating cols. Had BCP updated the tlb to the LP value then BCP would be in
the situation that the supposed tlb is higher than the value of the current LP
relaxation.

Another problem (as you guessed) arises when both cols and cuts are generated.
One would not want to do both in the same iteration (in fact, I'm not sure BCP
would expand the rows and cosl correctly, I have to check...) since in that
case adding the cuts to the formulation may mean that the already generated
cols are worthless and vice versa. Adding both the cuts and cols leads to I
don't know what, but definitely strange things :-). So... if the user does not
generate cuts and cols in the same iteration then there'll be iterations when
cols are not generated. But BCP has no way of knowing that it was impossible
to generate cols or the user decided not to do so in this iteration. And
checking for the existence of generated cuts is not enough either since it's
possible that the user tried to generate cuts and did not succeed.

So far I have argued for compute_lower_bound not updating the tlb. It is still
possible that a reordered sequence of calls would make more sense than the
current order. That I do not know. After all, you are right, that in the
current setup it's almost mandatory that the user generates the columns in
the compute_lower_bound method, saves the cols then returns them in the
generate_vars_in_lp method, and this seems a bit silly. The reason for the
current order lies in the multiprocess environment. Cols can be generated not
just in the generate_vars_in_lp method but in a separate process as well. It
seemed to me that if the user can come up with a tlb that enables the
fathoming of the node that would save the communication to the variable
generator process. On the other hand, if all variable generation is done first
then the computed tlb could be more accurate. So... I don't know. Reordering
the calls may be useful.

--Laci

On Wed, 26 Nov 2003, Matthew Galati wrote:

> 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/
> 
> 
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at www-124.ibm.com
> http://www-124.ibm.com/developerworks/oss/mailman/listinfo/coin-discuss
>