[Coin-discuss] Lower bounds in BCP

[Jörg Herbers]

Hi,

some time ago (on 12/16/2003), I posted a question regarding BCP lower bound 
handling. Obviously, BCP did not maintain a global lower bound, meaning that 
even if all further search tree nodes have lower bounds greater/equal to a 
known upper bound (or within some given distance to the upper bound), BCP 
does not directly terminate. However, the resulting tailing-off effect can 
be quite time-consuming.

I first tried to solve the problem by determining and storing one global 
lower bound (the value of the LP relaxation) in my BCP_lp_user-derived 
class. But this only allows for an early termination of actions in the user 
class while BCP still processes all nodes. Furthermore, global lower bounds 
are generally stronger and increase when upper search tree levels have been 
processed.

In the meantime, I have implemented a better global lower bound handling in 
BCP. BCP_tree::true_lower_bound() shows the basic idea, but this function 
traverses the whole tree and is only called once at the end of the search. 
The approach which I implemented is more efficient by maintaining active and 
candidate search nodes supporting the global lower bound.

Please let me know if you are interested in reviewing and integrating such a 
functionality.

Jörg

_________________________________________________________________
MSN 8 helps eliminate e-mail viruses. Get 2 months FREE*. 
http://join.msn.com/?page=features/virus