[Coin-discuss] Lower bounds in BCP

[Jörg Herbers]

I’m doing branch&price with BCP and I’m wondering about the lower bound 
handling. Every tm node holds a lower bound in true_lower_bound which can be 
modified by overriding BCP_lp_user::compute_lower_bound. I have two 
questions now:

1. In every iteration, compute_lower_bound is called before column 
generation is done. This implies that you cannot exploit knowledge on if 
columns were generated at all. If no columns were generated, a new lower 
bound equal to the current relaxation’s value could be returned. What is the 
standard way to exploit such knowledge?

2. If I understood BCP correctly, it currently doesn’t maintain a global 
lower bound (typically the value of the LP relaxation before any branching). 
When an integer solution equal to this lower bound is found, all further 
search could directly be interrupted. Instead, BCP processes all further 
nodes, doing column generation to obtain a lower bound on the node and 
fathoming the nodes. In large-scale applications, this can be quite 
time-consuming. Are there any means of implementing a global lower bound 
logic?

Thanks in advance,
Jörg

_________________________________________________________________
Add photos to your messages with MSN 8. Get 2 months FREE*. 
http://join.msn.com/?page=features/featuredemail